编程介的小学生 2019-06-12 19:50 采纳率: 20.5%
浏览 136

垃圾回收站的距离最短优化算法,怎么采用C语言的程序的代码编辑的方式去实现的步骤

Problem Description
As everyone knows, the garbage collecting station is very important to our daily life. With the growing of the city, more and more garbage need to be collected timely. First, let us see what will the garbage collecting station do everyday.
The station divide the city into N*M blocks, each block contains some buindings, as the picture below shows. And the garbage collecting station lies at the suburban district, but not inside any one of these blocks.

The station will sort the blocks (b1, b2, … bK, K = N*M )by their priority in a line. For instance, after the sort process, the blocks will be arranged as a sequence b1. b2. b3….bK, then the garbage collecting lorry will begin to collect garbage at b1, loading the garbage at b1, then go to b2, loading garbage then go to b3, and so on. After loaded the garbage at bK, the lorry will go to the station and upload all the garbage.

Now the station want to build another two stations, and these two stations will build inside two different blocks bi and bj (i<j). And the garbage of blocks b1 to bi will be carried to bi, the garbage of blocks bi+1 to bj will be carried to bj, the garbage of blocks bj+1 to bK will be carried to the station at the suburban district.

Now the problem is: we assume that carrying one unit of garbage in one meter will cost $1. Given the weight of the garbage of each block and the distance between bi and bi+1(1<=i<k), bk and the station, you should find out where to build the two new stations(i.e, choose two blocks bi and bj and make them as new stations) to make the cost as low as possible.

Input
Standard input will contain multiple test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.
The first line of each test case contains an integer N(1<=N<=10000), the number of blocks. N lines follow. The i-th line containing two integers, wi (the weight of garbage of block i, 1<=wi<=10000) and di(the distance between di and di+1, 1<=di<=10000), the last one dk means the distance between dk and the station.

Output
Results should be directed to standard output. For each case, output an integers S, the least $ we have to spend to carry the garbage to the collecting station.

Sample Input
1
4
1 2
2 1
3 3
1 1

Sample Output
3

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 求差集那个函数有问题,有无佬可以解决
    • ¥15 【提问】基于Invest的水源涵养
    • ¥20 微信网友居然可以通过vx号找到我绑的手机号
    • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
    • ¥15 解riccati方程组
    • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
    • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
    • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
    • ¥50 树莓派安卓APK系统签名
    • ¥65 汇编语言除法溢出问题