今天模考共5题
我在这里为大家分享下T4归零和T5游戏高手的思路
T4<20438>
读完题后 我们先写一个函数求x的数位和
int digit(int x){
int sum=0;
while(x!=0){
sum+=x%10;
x/=10;
}
return sum;
}
经过几秒钟的思考 我们发现当下x<10时只需操作1次
当x>=10时 操作数为当前数x-digit(x)的操作数+1
即
dp[x]=\begin{cases} 1 (x<10)\\ dp[x-digit(x)]+1 (x>=10) \end{cases}
具体代码如下
for(int i=1;i<10;i++){
dp[i]=1;
}
for(int i=10;i<=N;i++){
dp[i]=dp[i-digit(i)]+1;
}
T5<20439>
读完题后 我们直接输入排序二分三件套
sort(play+1,play+1+n,cmp);
int l=1,r=n;
while(l<r){
int mid=(l+r)/2;
if(check(mid)==true) r=mid;
else l=mid+1;
}
如此 代码大部分就结束了
接着就是整体中最难的地方了 check函数
为了使胜利人数尽可能多 我们应尽可能大的消耗耐受值大的玩家
我们可以让耐受值最大的玩家分别与耐受值第二大的玩家分别战斗
可以使耐受值最大的玩家的耐受值变得最小
(具体代码如下）
bool check(int mid){
long long int sum=0;
for(int i=n;i>=1;i--){
if(i==mid) continue;
if(sum==0) sum+=play[i].a;
else sum=(sum+play[i].a)/2;
}
return sum<=play[mid].a;
}
