CF-158
这次比赛较上次也是有进步，成功地多AC了一道题。但第4题也是很遗憾只差一点了。
A. Line Trip
题意：车在数轴上从$0$点到达$x$点又返回$0$点，有$k$点的油，可以走$k$个单位，在数轴上$a_1,a_2,a_3...a_n$处可以加油到$k$点，$0$点处和$x$点处无法加油，问$k$的最小值。
思路：那么根据题意我们可以很好地考虑出$k$的最小值，即两个加油点之间的距离的最大值，所以$k=max(a_1-0,a_2-a_1,...,a_n-a_{n-1}))$,同时我们还要记得考虑从$a_n$点到$x$点又返回$a_n$点的距离$2*(x-a_n)$。
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int N=1e2+2;
int t;
int n,x;
int a[N];
int ans;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>t;
while(t--)
{
ans=0;
cin>>n>>x;
for(int i=1;i<=n;i++) cin>>a[i],ans=max(ans,a[i]-a[i-1]);
ans=max(2*(x-a[n]),ans);
cout<<ans<<endl;
}
return 0;
}
B. Chip and Ribbon
题意:芯片从$1$点到$n$点，有两种移动方式：
- 从$i$点到$(i+1)$点
- 随意到$1$至$n$的任意一点且耗费$1$次转移次数
芯片每到一点该点的标量加$1$，求使得$1$至$n$点的值变成$a_1,a_2...a_n$的最小转移次数为多少？
思路:我们可以容易得到在一段单调递减的数列中最小的转移次数是第一个值减去$1$。那么在连续的两段单调递减的数列中第一段的答案仍一样，而第二段的答案则为其第一个值减去前一个值，两者相加得到答案。如果碰到$0$则将加上记录的值。
那么我们可以推出答案为每段单调递减的数列的答案之和。
得到代码:
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
typedef long long ll;
int t;
int n,c[N];
ll ans;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>t;
while(t--)
{
ans=0;
cin>>n;
for(int i=1;i<=n;i++) cin>>c[i];
c[n+1]=0;//记录答案
ll s=0;
for(int i=1;i<=n+1;i++)
{
if(!c[i]) ans+=s,s=0;
else if(c[i]>c[i-1])
s+=c[i]-c[i-1];
}
cout<<ans-1<<endl;
}
return 0;
}
C. Add, Divide and Floor
题意：给定一个数列$a_1,a_2...a_n$，对每一个数进行一次操作:将$a_i$改为$\lfloor \frac{a_i+x}{2}\rfloor$($0 \le x \le 10^{18}$)。求最少次数$k$使得数列的每一个数都相等，且若$k \le n$,则输出$x$的数列。
思路:由于除以$2$，所以$x$只与就相关，也就只考虑$1$与$0$即可。再考虑$a_i$的奇偶性:
- 若$a_i$为奇数，$x$为$1$时，$a_i$变为$\lfloor \frac{a_i}{2} \rfloor+1 $, $x$为$0$时，$a_i$变为$\lfloor \frac{a_i}{2} \rfloor$。
- 若$a_i$为偶数，不管$x$为$1$还是$0$，$a_i$都变为$\frac{a_i}{2}$。
而对于整个数列我们只需考虑最大值$MX$和最小值$MN$达成一致。那$MX$为奇数则$x=0$，否则再看$MN$，若为奇数则$x=1$，反之则无所谓，假设为$x=0$。由于得到不断除以$2$直到$0$，绝对保证相等，时间复杂度为$O(log(MX))$。
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int t,n;
int a[N];
int ans[N];
int mn,mx;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>t;
while(t--)
{
cin>>n;
mn=INT_MAX,mx=0;
for(int i=1;i<=n;i++) cin>>a[i],mn=min(a[i],mn),mx=max(a[i],mx);
if(mn==mx)
{
cout<<0<<endl;//若值都相等，那么直接输出0
continue;
}
int k=0;
while(mn!=mx)
{
if(mx%2)
{
ans[++k]=0;
mx/=2,mn/=2;
}
else if(mn%2)
{
ans[++k]=1;
mx/=2,mn=mn/2+1;
}
else
{
ans[++k]=0;
mx/=2,mn/=2;
}
}
cout<<k<<endl;
if(k<=n)
{
for(int i=1;i<=k;i++) cout<<ans[i]<<" ";
cout<<endl;
}
}
return 0;
}
D. Yet Another Monster Fight
题意：魔法师瓦夏要击败$n$个怪兽，生命值分别为$a_1,a_2...a_n$，他会挑选一个怪兽攻击，伤害为$k$，若$k>=a_i$，则该怪物被击败，同时会随机攻击已经攻击的怪兽旁边的怪兽，一共攻击$n$次，伤害会递减。瓦夏希望凸显自己的强大，要求伤害最小值能击败所有怪兽。
思路：明显伤害越高，则击败所有怪物的可能性越高，具有单调性，可以考虑二分(到这一步赛上都想到了，可惜接下来的check函数思路错了)。
check()函数可以枚举每一个点作为初始点$i$，再判断是否可行。
由题意知：
- 若$j<i$，那么最坏情况下$[j+1,n]$的点都要被打倒，那么此时伤害已经递减为$k-n+j$，那么可以被击倒的话则有$a_j \le k-n+j$，即$a_j-j \le k-n$
- 若$j>i$，那么最坏情况下$[j-1,n]$的点都要被打倒，那么此时伤害已经递减为$k-n+j$，那么可以被击倒的话则有$a_j \le k-j+1$，即$a_j+j \le k+1$
那么我们可以用数组预处理出$i$点前的$a_j-j$的最大值和$i$点后的$a_j+j$的最大值。
那么得到代码：
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
typedef long long ll;
int n;
ll a[N];
ll pre[N],aft[N];
bool check(ll k)
{
for(int i=1;i<=n;i++)
{
if(a[i]<=k&&pre[i-1]<=(k-n)&&aft[i+1]<=(k+1))
return true;
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
pre[i]=max(pre[i-1],a[i]-i);
for(int i=n;i>=1;i--)
aft[i]=max(aft[i+1],a[i]+i);
ll l=0,r=1e18;
ll ans=0;
while(l<=r)
{
ll mid=(l+r)>>1;
if(check(mid)) r=mid-1,ans=mid;
else l=mid+1;
}
if(check(r))
ans=min(r,ans);
cout<<ans;
return 0;
}