【2019杭電多校第一場1004=HDU 6581】Vacation(思考+タイムアウト回避)
4696 ワード
タイトルアドレス:http://acm.hdu.edu.cn/showproblem.php?pid=6581
タイトル:
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Problem Description
Tom and Jerry are going on a vacation. They are now driving on a one-way road and several cars are in front of them. To be more specific, there are n cars in front of them. The ith car has a length of li, the head of it is si from the stop-line, and its maximum velocity is vi. The car Tom and Jerry are driving is l0 in length, and s0 from the stop-line, with a maximum velocity of v0. The traffic light has a very long cycle. You can assume that it is always green light. However, since the road is too narrow, no car can get ahead of other cars. Even if your speed can be greater than the car in front of you, you still can only drive at the same speed as the anterior car. But when not affected by the car ahead, the driver will drive at the maximum speed. You can assume that every driver here is very good at driving, so that the distance of adjacent cars can be kept to be 0. Though Tom and Jerry know that they can pass the stop-line during green light, they still want to know the minimum time they need to pass the stop-line. We say a car passes the stop-line once the head of the car passes it. Please notice that even after a car passes the stop-line, it still runs on the road, and cannot be overtaken.
Input
This problem contains multiple test cases. For each test case, the first line contains an integer n (1≤n≤105,∑n≤2×106), the number of cars. The next three lines each contains n+1 integers, li,si,vi (1≤si,vi,li≤109). It's guaranteed that si≥si+1+li+1,∀i∈[0,n−1]
Output
For each test case, output one line containing the answer. Your answer will be accepted if its absolute or relative error does not exceed 10−6. Formally, let your answer be a, and the jury's answer is b. Your answer is considered correct if |a−b|max(1,|b|)≤10−6. The answer is guaranteed to exist.
Sample Input
1 2 2 7 1 2 1 2 1 2 2 10 7 1 6 2 1
Sample Output
3.5000000000
5.0000000000
問題解決の考え方:
最後の車の先頭がstop線に到着した場合、以下のn+1の場合があります. n->0両が連結して通過し、n両目は車隊のヘッド 第n-1両は第n両に追いつかなかった、n-1--> 0両が連結して通過し、n-1両目は車隊のヘッド である第n-2両は第n-1両に追いつかず、n-2 --> 0両が連結して通過し、n-2両目は車隊のヘッド ........ 第0両は第1両に追いつかず、0--> 0台の車が連なって通過し、0台目の車は車隊のヘッド すなわち,このn+1台の車l,s,vが与えられていない場合,各車が先頭として通過する可能性があり,対応する通過時間が算出される.
与えられたn+1台の車のl,s,vに対して,これらのデータをそれぞれ上記n+1種に持ち込む場合,必ず1種が実際に発生し,最大値をとることが答えである.
長い間考えていても、なぜ最大値を取ったのかを徹底的に考えていませんでした.第1に、与えられた第2の例を参照して結論を出すことができる. は、車を追う戦略に依存している.題意によると、どの車もその最大速度で前の車(追いつくことができるのは、必ず後の車の速度が前の車の速度より大きい)を追いかけ、追いついて減速して前の車の速度になるので、全体的に速度は減少傾向にあり、実際の結果に対応する時間が最大となる.
厳密な証明はまだ考えていません.討論を歓迎します.
!!!タイムアウトする2つの小さな点⚠️!!!:
(1)cinで読まないで、ios::sync_と書いてもwith_stdio(false); タイムアウトして、書きます
やはりタイムアウトになるので、あきらめてcinで読み込みましょう.本当に仕方がないときはcinを使いましょう!!
(2)本題は複数組入力していますが、最大何組のテストサンプルを与えていません.もし各テストサンプルがmemsetしていたら、時間複雑度O(ke 5)、kはテスト回数で、私はこのように書いて、Tになりました.このような状況をできるだけ避けましょう.複数のテストはmemsetを慎みましょう.
時間複雑度:O(
n), n n問題では範囲
が与えられており,特定はタイムアウトしない.
acコード:
タイトル:
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Problem Description
Tom and Jerry are going on a vacation. They are now driving on a one-way road and several cars are in front of them. To be more specific, there are n cars in front of them. The ith car has a length of li, the head of it is si from the stop-line, and its maximum velocity is vi. The car Tom and Jerry are driving is l0 in length, and s0 from the stop-line, with a maximum velocity of v0. The traffic light has a very long cycle. You can assume that it is always green light. However, since the road is too narrow, no car can get ahead of other cars. Even if your speed can be greater than the car in front of you, you still can only drive at the same speed as the anterior car. But when not affected by the car ahead, the driver will drive at the maximum speed. You can assume that every driver here is very good at driving, so that the distance of adjacent cars can be kept to be 0. Though Tom and Jerry know that they can pass the stop-line during green light, they still want to know the minimum time they need to pass the stop-line. We say a car passes the stop-line once the head of the car passes it. Please notice that even after a car passes the stop-line, it still runs on the road, and cannot be overtaken.
Input
This problem contains multiple test cases. For each test case, the first line contains an integer n (1≤n≤105,∑n≤2×106), the number of cars. The next three lines each contains n+1 integers, li,si,vi (1≤si,vi,li≤109). It's guaranteed that si≥si+1+li+1,∀i∈[0,n−1]
Output
For each test case, output one line containing the answer. Your answer will be accepted if its absolute or relative error does not exceed 10−6. Formally, let your answer be a, and the jury's answer is b. Your answer is considered correct if |a−b|max(1,|b|)≤10−6. The answer is guaranteed to exist.
Sample Input
1 2 2 7 1 2 1 2 1 2 2 10 7 1 6 2 1
Sample Output
3.5000000000
5.0000000000
問題解決の考え方:
最後の車の先頭がstop線に到着した場合、以下のn+1の場合があります.
与えられたn+1台の車のl,s,vに対して,これらのデータをそれぞれ上記n+1種に持ち込む場合,必ず1種が実際に発生し,最大値をとることが答えである.
長い間考えていても、なぜ最大値を取ったのかを徹底的に考えていませんでした.
厳密な証明はまだ考えていません.討論を歓迎します.
!!!タイムアウトする2つの小さな点⚠️!!!:
(1)cinで読まないで、ios::sync_と書いてもwith_stdio(false); タイムアウトして、書きます
cin.tie(nullptr);
cout.tie(nullptr);やはりタイムアウトになるので、あきらめてcinで読み込みましょう.本当に仕方がないときはcinを使いましょう!!
(2)本題は複数組入力していますが、最大何組のテストサンプルを与えていません.もし各テストサンプルがmemsetしていたら、時間複雑度O(ke 5)、kはテスト回数で、私はこのように書いて、Tになりました.このような状況をできるだけ避けましょう.複数のテストはmemsetを慎みましょう.
時間複雑度:O(
n), n n問題では範囲
が与えられており,特定はタイムアウトしない.acコード:
#include
using namespace std;
const int maxn = 100010;
typedef long long ll;
double sum[maxn];// sum[i] i stop
double n, l, s, v, ans;
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
while(~scanf("%lf", &n))
{
sum[0] = 0;
for(int i = 0; i <= n; i++)
{
scanf("%lf", &l);
if(i) sum[i] = sum[i - 1] + l;
}
for(int i = 0; i <= n; i++)
{
scanf("%lf", &s);
sum[i] += s;
}
ans = 0;
for(int i = 0; i <= n; i++)
{
scanf("%lf", &v);
ans = max(ans, sum[i]/v);
}
printf("%.10lf
", ans);
}
return 0;
}