Preface

补一篇好久之前打的CF的博客，说实话其实B题我当时怎么想的已经忘的七七八八了

这场第一眼看A没啥思路，就先去把B这个构造写了，中间想了挺久的大概40min才写出来

然后回头一看A发现可以倒着做，就是个丁真题了然后15min写完

后面看C刚开始以为是个贪心，后面又感觉是个DP，但状态数比我预计的多，搞来搞去也没写出来

后面看Tutorial才发现原来是带悔贪心，捏麻麻的好像自从ZJOI2020那道题之后就再也没见到过这个算法的题了，苦路西

A. Ntarsis' Set

正着想不太好搞（其实也能做），安利一手徐神的正序的\(O(n)\)做法——CF1852A 中的结论证明

其实不妨倒着考虑问题，我们不妨将进行了\(i\)次删数操作的集合称为版本\(i+1\)，则我们现在要求的是版本\(k+1\)中第一小的元素

那么倒着想这个元素其实就是版本\(k\)中第一个没有出现的元素，我们记此时它的位次为\(rk\)

那么再往前推一步这个元素其实就是版本\(k-1\)中第\(rk\)个没有出现的元素，不难发现可以一路推回到版本\(1\)中第几个没有出现的元素

具体实现可以直接用一个指针来单调移动，但比赛的时候我降智了写了个二分，不过无伤大雅

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
const int N=200005;
int t,n,k,a[N],cnt,num[N],l[N],r[N],pfx[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i; for (scanf("%lld%lld",&n,&k),cnt=0,i=1;i<=n;++i)
		if (scanf("%lld",&a[i]),a[i]>a[i-1]+1)
		num[++cnt]=a[i]-a[i-1]-1,l[cnt]=a[i-1]+1,r[cnt]=a[i]-1;
		for (i=1;i<=cnt;++i) pfx[i]=pfx[i-1]+num[i];
		int ret=1; for (i=1;i<=k;++i)
		{
			int pos=lower_bound(pfx+1,pfx+cnt+1,ret)-pfx;
			if (pos>cnt) { ret=a[n]+ret-pfx[cnt]; continue; }
			ret=l[pos]+(ret-pfx[pos-1]-1);
		}
		printf("%lld\n",ret);
	}
	return 0;
}

B. Imbalanced Arrays

原谅我这题真忘了我当时怎么想的了，就说一个大概的印象吧

首先我们将\(a_i\)从大到小排序，同时我们设数组\(b_i\)表示对于每一个\(a_i\)，我们都对\(b_1\sim b_{a_i}\)进行区间加\(1\)操作

则若\(\exist i\in[1,n],a_i\ne b_i\)则一定无解，不难发现这是充要条件

否则我们可以找到一个分界点\(pos\in[1,n]\)，满足\([1,pos]\)中所有数最后取值都是正的，而\([pos+1,n]\)中所有数最后取值都是负的

由于最后数的值域是\([-n,n]\)，我们不妨从\(n\)到\(1\)枚举每个数，然后考虑每次要么将正的这个数放在前面部分，要么将负的这个数放在后面部分

具体放在哪边的话可以把贡献的式子写出来和目标的式子对比一下，不难发现这样一定可以构造出一组合法的解

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
const int N=200005;
int T,n,a[N],b[N],ans[N]; pi t[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&T);T;--T)
	{
		RI i,j,k; for (scanf("%d",&n),i=0;i<=n;++i) b[i]=0;
		for (i=1;i<=n;++i) scanf("%d",&a[i]),++b[1],--b[a[i]+1],t[i]=pi(a[i],i);
		for (i=1;i<=n;++i) b[i]+=b[i-1]; bool flag=1;
		for (sort(t+1,t+n+1,greater<pi>()),i=1;i<=n&&flag;++i) if (t[i].fi!=b[i]) flag=0;
		if (!flag) { puts("NO"); continue; }
		int pos=n; for (i=1;i<=n;++i) if (b[i]<=i-1) { pos=i; break; }
		for (puts("YES"),i=1,j=n,k=n;k>=1;--k)
		if (i+(k-1)==b[i]) ans[t[i++].se]=k; else ans[t[j--].se]=-k;
		for (i=1;i<=n;++i) printf("%d%c",ans[i]," \n"[i==n]);
	}
	return 0;
}

C. Ina of the Mountain

首先考虑以下经典问题，给定数列\(\{a_n\}\)，每次可以选择将一个区间内的所有数减去\(1\)，求最后最少的操作次数使得所有数为\(0\)

根据差分我们容易知道最后的答案其实就是\(\sum_{i=1}^n \max(0,a_i-a_{i-1})\)，但这道题相当于是可以将每个数加上若干个\(k\)，求上述式子的最小值

考虑以下贪心的想法，首先不妨设\(a_i\)与\(a_{i-1}\)加上的\(k\)的数量相同，则此时：

若\(a_i<a_{i-1}\)，则上述式子的贡献为\(0\)，贪心地认为不动是最优的
若\(a_i\ge a_{i-1}\)，则有两种情况：
- 不做其它修改，此时对答案的贡献为\(a_i-a_{i-1}\)
- 将\(t\in[j,i)\)的所有\(a_t\)都加上\(k\)，不难发现此时对答案的贡献为\(a_j-a_{j-1}+k\)

由于我们每次要求出当前的最优代价，因此考虑将对\([j,i)\)操作的这种方案视为反悔操作，用一个小根堆来维护所有反悔操作的最小贡献即可

要注意的是若我们选择在\(i\)这个时候反悔选择对\([j,i)\)进行操作，那么后续反悔选择在\(i\)这个位置时要额外付出的代价其实是\(a_i-a_{i-1}\)而非\(a_i-a_{i-1}+k\)，因为\(a_{i-1}\)的值已经比原来的大\(k\)了

剩下的细节看代码吧，复杂度\(O(n\log n)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<limits.h>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
const int N=200005;
int t,n,k,a[N]; LL ans;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		priority_queue <int,vector <int>,greater <int>> hp;
		RI i; for (scanf("%d%d",&n,&k),i=1;i<=n;++i) scanf("%d",&a[i]);
		for (ans=0,i=1;i<=n;++i)
		{
			int now=a[i]%k,pre=a[i-1]%k;
			if (now<pre) hp.push(now+k-pre); else
			hp.push(now-pre),ans+=hp.top(),hp.pop();
		}
		printf("%lld\n",ans);
	}
	return 0;
}