题目链接:2017 ACM-ICPC 东亚总决赛 C:Traffic Light
Description
一个人从家到公司一共要经过个红绿灯。从第
个红绿灯到第
个红绿灯需要花费
秒（假设家再第
个红绿灯，公司在第
个红绿灯），第
个红绿灯绿灯时长为
，红灯时长为
。保证所有的
相等，即红绿灯的周期相等。现在你能够调整所有红绿灯的相位，使得这个人在最坏情况下从家到公司所需时间最少，求最少是多少？
Sample Input
2
1
30 70
15 15
2
30 15 70
10 20
20 10
Sample Output
Case #1: 115.000000
Case #2: 135.000000
Solution
由于你能够调整所有红绿灯的相位
所以在路上花的时间不会对他等红绿灯的时间造成影响
所以只需要考虑如何调整使得在最坏情况下等红绿灯的时间最短
容易想到,这个时间为。
Code
#include<map>
#include<set>
#include<list>
#include<queue>
#include<vector>
#include<string>
#include<time.h>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
//#define Judge
//#define Online
#define reg register
#define ll long long
#define mod 1000000007
#define inf 2147483647
#define lowbit(x) ((x)&-(x))
#define abs(x) ((x)<0?-(x):(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define ckmax(a,b) ((a)=max((a),(b)))
#define ckmin(a,b) ((a)=min((a),(b)))
using namespace std;
#ifdef Judge
#define puts io.put
#define getchar io.gc
#define putchar io.wchar
#ifdef Online
FILE*in=stdin;
FILE*out=stdout;
#else
FILE*in=fopen(".in","r+");
FILE*out=fopen(".out","w+");
#endif
struct FastIO{
#define S 1000000
int wpos,len,pos;char wbuf[S],buf[S];
FastIO(){wpos=0,len=0,pos=0;}
inline char gc(){
if (pos==len) pos=0,len=fread(buf,1,S,in);
if (pos==len) return 0; return buf[pos++];
}
inline void wchar(int x) {
if (wpos==S) fwrite(wbuf,1,S,out),wpos=0;
wbuf[wpos++]=x;
}
inline void put(const char*s) {for(; *s; ) wchar(*s++);}
~FastIO() {
if (wpos) fwrite(wbuf,1,wpos,out),wpos=0;
}
}io;
#endif
template<typename T> inline void read(T&x){T f=1;x=0;char c;
for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f;
for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f;
}
template<typename T> inline void wt(T x,char c=0){char ch[(sizeof(T)+1)<<1];if (x<0) x=-x,putchar('-');
int t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!=0) putchar(c);
}
int main(int argv,char*argc[]){
int T;read(T);
for (int Cas=1; Cas<=T; Cas++) {
int n;read(n); double ans(0),Max(0),t;
for (int i=0; i<=n; i++) scanf("%lf",&t),ans+=t;
for (int i=0; i<n; i++) scanf("%*lf%lf",&t),Max=max(Max,t);
printf("Case #%d: %.10lf\n",Cas,ans+Max);
}
return 0;
}
