[gym102832L][CCPC2020 长春站 L]Coordinate Paper

本文主要是介绍[gym102832L][CCPC2020 长春站 L]Coordinate Paper，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Coordinate Paper

题解

很简单的一道构造题。

我们发现，相邻两个数可以转化成 $a_{i}+1 \equiv a_{i+1}(mod\, k+1)$ 的关系。
所以我们可以考虑先构造出一组符合要求的最小解，对于可以向上加的点加上 $k + 1$ 去构造解，使得这组解得总和与 $s$ 模 $n$ 的余数一样。
之后我们可以通过整体的加减得到一组和为 $s$ 的解。
构造一组最小的解可以通过 $a_{i}=(i-1)\%(k+1)$ 的方法得到。
对于一组合法的解，如果它两边的数的值都比它大，它就可以加上 $k + 1$ ，得到另外一组合法的解。
我们可以通过这种方法去执行不超过 $n$ 次操作，如果不能构造出一组与 $s$ 模 $n$ 值一样的解，就说明我们永远也构造不出解。
因为最后构造出的与 $s$ 模 $n$ 值一样的解可能大于 $s$ ，这个时候会涉及到减法，为尽可能让所有数的值都不小于0，我们之前给数加上 $k + 1$ 时应当选择最小的一个数去给它加，这样可以保证我们整个数列的最小值一直都在提高，竟可能地不会出现小于0的情况。

时间复杂度 $O\left(nlog\,n\right)$ 。

源码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
using namespace std;
#define MAXN 100005
#define lowbit(x) (x&-x)
#define reg register
typedef long long LL;
#define int LL
const int INF=0x7f7f7f7f;
typedef unsigned long long uLL;
typedef pair<LL,LL> pii;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=getchar();while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;
}
LL n,k,s,a[MAXN],sum;
bool vis[MAXN];
struct ming{LL id,val;bool friend operator < (const ming &x,const ming &y){return x.val>y.val;}
};
priority_queue<ming> q;
signed main(){read(n);read(k);read(s);a[1]=0;if(n==1){printf("%lld\n",s);return 0;}for(int i=2;i<=n;i++)a[i]=(a[i-1]+1LL)%(k+1LL),sum+=a[i];a[n+1]=INF; if(a[1]<a[2])q.push((ming){1,a[1]}),vis[1]=1;for(int i=2;i<=n;i++)if(a[i]<a[i-1]&&a[i+1]>a[i])q.push((ming){i,a[i]}),vis[i]=1;if(sum>s){puts("-1");return 0;}int tim=0;while(!q.empty()&&((s-sum)%n)){int u=q.top().id;q.pop();vis[u]=0;a[u]+=k+1LL;sum+=k+1LL;if(u<n&&a[u+1]<a[u+2]&&a[u+1]<a[u]&&!vis[u+1])q.push((ming){u+1,a[u+1]}),vis[u+1]=1;if(u>1&&a[u-1]<a[u-2]&&a[u-1]<a[u]&&!vis[u-1])q.push((ming){u-1,a[u-1]}),vis[u-1]=1; if(q.empty()&&a[1]<a[2])q.push((ming){1,a[1]});tim++;if(tim>n)break;}if(sum%n!=s%n){puts("-1");return 0;}LL tmp=(s-sum)/n;for(int i=1;i<=n;i++)a[i]+=tmp;for(int i=1;i<=n;i++)if(a[i]<0){puts("-1");return 0;}for(int i=2;i<=n;i++)if(a[i]!=a[i-1]-k&&a[i]!=a[i-1]+1LL){puts("-1");return 0;}for(int i=1;i<=n;i++)printf("%lld ",a[i]);puts("");return 0;
}