2014
11-30

# Hard Rode

The road to Shu is hard, even harder than climbing to the blue sky. A poem by Li Po from Tang Dynasty 1,200 years ago described the difficulty in travelling into Sichuan.

However the above old saying is no longer true as a convenient communication network of railway, highway, waterway and air transport has come into being. Railways cover a total mileage of 2,693 km, consisting of five trunk lines including the BaojiChengdu and Chengdu-Chongqing railways, eight feeder lines and four local railways. The total mileage of highways stretches to nearly 80,000 km, ranking at the forefront in China. Now a highway network with the provincial capital of Chengdu as the center radiating to all cities in the province has been formed. A total of 500 km of expressways have been built. It is very easy to transfer passengers and freights between Sichuan and other provinces. After a nationwide railway speed acceleration launched in last year, trains can be allowed to run at a speed above 120 km per hour. However, the average speed of a train depends on its make-up. There is only single railway track between stations from Baoji to Chengdu, A primary task for dispatchers is to arrange for trains to meet and pass each other. You are requested to write a program to make the arrangement for a series of trains of different speeds from one station to its next station in the least amount of time.

What you should pay attention to while writing this program is that since there is a single railway track from Baoji to Chengdu, two trains are not allowed to pass the same spot at the same time, or they would be collision, and that because of the limited staff, there should be a fixed interval time between two trains out of the station, what’s more, the trains could pull into the station at the same time, but never get out at the same time.

The input consists of several test cases. Each test case begins with a line containing 3 integers L (1<=L<=100000) , N (1<=N<=8) and T (1 < T < 10000) which indicate the distance between two stations (unit is meter), the number of trains, as well as the interval time of adjacent trains when trains leave the start (unit is second).

The next N lines contain average speeds of N trains (unit is m/s).

A single line with L = 0 indicates the end of input file and should not be processed by your program.

The input consists of several test cases. Each test case begins with a line containing 3 integers L (1<=L<=100000) , N (1<=N<=8) and T (1 < T < 10000) which indicate the distance between two stations (unit is meter), the number of trains, as well as the interval time of adjacent trains when trains leave the start (unit is second).

The next N lines contain average speeds of N trains (unit is m/s).

A single line with L = 0 indicates the end of input file and should not be processed by your program.

100000 6 300
3
4
5
6
2
1
0

Case 1: 101500

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

#define INF 0x3f3f3f3f

int a[8];

int main() {
int l, n, t, cas = 1;
while(scanf("%d", &l), l) {
scanf("%d%d", &n, &t);
for(int i = 0; i < n; ++i) scanf("%d", a + i);
sort(a, a + n);
int res = INF;
do {
int maxi = 0;
bool flag = true;
for(int i = 0; i < n; ++i) {
int temp = i * t + (double)l / a[i] + 0.5;
if(temp < maxi) flag = false;
maxi = temp;
}
if(flag)
res = min(res, maxi);
} while(next_permutation(a, a + n));
printf("Case %d: %d\n", cas++, res);
}
return 0;
}

1. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

2. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1))；因为第二种解法如果数组有重复元素 就不正确

3. 问题3是不是应该为1/4 .因为截取的三段，无论是否能组成三角形， x， y-x ，1-y,都应大于0，所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.