https://codeforces.com/contest/1853
C题感觉很不好写的样子，首先通过打表发现最后答案每次都是+n，那么我们考虑前i个，假如当前的ans+i仍然小于a[i+1]，则没有影响，我们依然可以直接往后跳，否则，我们越过了a[i+1]，那么我们应当加上i+1，注意，这有可能会导致往后面继续跳，
比如1 3 5 6 7，我们跳到4之后，4+2>5,所以应当+3，4+3>6,应当+4，4+4>7,应当+5，4+5=9,结束。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<queue>
#define A puts("YES")
#define B puts("NO")
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const ll mo=1e9+7;
const int inf=1<<30;
const int N=2e5+5;
ll n,k,a[N],ans,x;
int main()
{
// freopen("data.in","r",stdin);
// freopen("ans.out","w",stdout);
int T;
scanf("%d",&T);
while (T--){
scanf("%lld %lld",&n,&k);
fo(i,1,n) scanf("%lld",&a[i]);
if (a[1]!=1) {
printf("%d\n",1);
continue;
}
ans=1;
int j=1;
while (j<n){
if (!k) break;
x=(a[j+1]-ans)/j;
if ((a[j+1]-ans)%j==0) x--;
if (x<=k) {
k-=x;
ans+=x*j;
}
else {
ans+=k*j;
k=0;
}
if (k) {
while (j<n && ans+j+1>=a[j+1]) {
j++;
if (j<n && ans+j<a[j+1]) break;
}
ans+=j;
k--;
}
}
if (k) ans+=n*k;
printf("%lld\n",ans);
}
return 0;
}
写了一坨答辩
D首先将a从大到小排序，首先非常显然，我们最后给他们安排的数一定是不增的，
对于当前的区间l，r发现只有当al'=now,或者ar‘=0时才有解，al’，ar‘，为减去前面已经确定的较大的正数的个数，递归处理即可。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<queue>
#define A puts("YES")
#define B puts("NO")
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const ll mo=1e9+7;
const int inf=1<<30;
const int N=2e5+5;
struct node{
int x,id;
};
node b[N];
int n,ans[N],flag;
bool cmp(node a,node b){
return a.x>b.x;
}
void solve(int l,int r,int now,int p){
if (l>r) return;
if (b[l].x-p==now) {
ans[b[l].id]=now;
solve(l+1,r,now-1,p+1);
}
else if (b[r].x-p==0){
ans[b[r].id]=-now;
solve(l,r-1,now-1,p);
}
else flag=0;
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("ans.out","w",stdout);
int T;
scanf("%d",&T);
while (T--){
scanf("%d",&n);
fo(i,1,n) {
scanf("%d",&b[i].x);
b[i].id=i;
}
sort(b+1,b+n+1,cmp);
flag=1;
solve(1,n,n,0);
if (!flag) {
B; continue;
}
A;
fo(i,1,n) printf("%d ",ans[i]);
printf("\n");
}
return 0;
}