CF 1157D N Problems During K Days
题目链接
题面
题目大意
Polycarp想要在 k 天做 n 道题，并且他希望每一天做的题量大于前一天的题量并且小于前一天题量的二倍。求是否可以满足条件，若满足，每天题量是多少。
题目分析
第 i 天至少做 i 道题才可以满足每一天的做题量大于前一天。如果前 k 天的和大于 n 说明无法满足题意。
天数越大，则其可以增加的数量范围越大。
be 表示当前天数，从 1 开始。
当剩余题量 tmp 大于剩余天数 (k - be + 1) 时，如果从小于前一位题数的二倍的地方 i 开始一直到第 k 天题量加 x ，更新剩余题量 tmp ，更新后当前位可以满足题意，则后面的天数仍可满足题量要求。x 即为前一位的二倍与当前位的差值——（num [ i - 1 ] * 2 - num[ i ]）和剩余题量除以剩余天数——（tmp / ( k - be + 1)）的最小值。
否则将当前可以满足题意的开始下标置为 k - 剩余题量tmp + 1，并更新从此处到 k 的题量。如果当前天数 be 的题量已经为前一天题量的二倍，将 be 后移。
一直循环直到剩余题量 tmp 为 0 ，或当前天数 be > k。
最后遍历数组判断是否满足题意即可。
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,k,num[100010];
int main()
{
scanf("%d%d",&n,&k);
int tmp=n,flag=1;
for(int i=1;i<=k;i++){
num[i]=i;
tmp-=i;
if(tmp<0){
flag=0;break;
}
}
int be=1;
while(tmp>0&&be<=k){
int add=min(tmp/(k-be+1),2*num[be-1]-num[be]);
if(be==1) add=tmp/(k-be+1);
if(add==0){
if(tmp/(k-be+1)==0) be=k+1-tmp;
if(be==1||(be>1&&2*num[be-1]-num[be]<=0)) be++;
continue;
}
for(int i=be;i<=k;i++){
if(i==1||(i>1&&num[i]+add<=2*num[i-1])){
num[i]+=add;
tmp-=add;
}
}
}
int sum=0;
for(int i=1;i<=k;i++){
sum+=num[i];
if(i>1&&(num[i]<=num[i-1]||num[i]>num[i-1]*2)){
flag=0;
}
}
if(sum!=n) flag=0;
if(flag){
printf("YES\n");
for(int i=1;i<=k;i++){
if(i!=1) printf(" ");
printf("%d",num[i]);
}
}
else printf("NO\n");
return 0;
}