Codeforces Round 887 (Div. 2)

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;
}