手速场,,一小时写完四题心满意足睡觉,起来一看E题rated的就过了一个。直接1760了,也是给我偷到分了
B:https://codeforces.com/contest/2055/problem/B
如果有两个$a[i]<b[i]$,那么模拟一下发现永远不能成功。
于是最多只有一个$a[i]<b[i]$,那么看看别的能不能把a[i]变成b[i]即可。
D:https://codeforces.com/contest/2055/problem/D
要点在于,发现稻草人移动的最佳方式。
对于第一个稻草人,需要先移动到0点让乌鸦传送,然后推着乌鸦往前走。
对于第二个稻草人,需要尽快让乌鸦传送。因为它传送之后,它会推着乌鸦往前走。
以此类推。
所以你会发现,下一个稻草人的最佳位置就是上一个稻草人的位置+k。如果时间不允许移动到这个位置,它也会在离这个位置最近的地方。有了这个思路,我们开始模拟:
我们记录当前已用时间t,当前位置cur。
1.对于第一个稻草人,先移动到0点让乌鸦传送
2.对于其他稻草人,有可能已经到达l点了,判断一下。
3.对于除第一个以外的稻草人,先判断这个稻草人在t时刻的位置。
4.如果$a[i]>=cur$,那就是乌鸦和当前稻草人双向奔赴,然后传送。
5.如果$a[i]<cur$,那就是乌鸦传送一下,然后在后面继续被推着往前。
6.最后如果遍历完所有稻草人,还没有到达l,那就乌鸦被推着到达l。
突然发现一个点,,在4步中,如果双向奔赴的过程中乌鸦到达了l点这个情况没有判断,但是懒得改了,也没有被hack。。。 :)
void solve(){
ll n,k;
double l;
cin>>n>>k>>l;
vector<double> a(n+1);
for(int i=1;i<=n;i++) cin>>a[i];
vector<double> oa(a);
double t = 0;
double cur = 0;
for(int i=1;i<=n;i++){
if(cur>=l){
break;
}
if(i==1){
t += a[i];
cur += k;
}else{
if(a[i] > cur){
a[i] = max(a[i]-t,cur);
double nt = abs(a[i]-cur)/2;
t += nt;
cur += nt;
cur += k;
}else if(a[i] <= cur){
a[i] = min(a[i] + t,cur);
cur = max(cur,a[i] + k);
}
}
}
if(cur < l){
t += (l-cur);
}
cout<<(int)(t*2)<<endl;
}