解题思路
观察可以发现,每次操作后序列元素之和不变,那么我们可以将每一次操作看作是 \(a_i\) 向 \(a_j\) 移动了 \(i\times x\)。由此可得,若序列和 \(sum\bmod n\not=0\),那么一定无解,否则一定存在一个合法的操作方案。
因为每次移动时移动的数应为 \(i\) 的倍数,所以 \(a_1\) 可以向任意元素移动任意大小不超过 \(a_1\) 的数,那么我们考虑先将所有数全部移动到 \(a_1\),再由 \(a_1\) 平分给 \(a_2,\dots,a_n\)。但是这种情况先可能存在一个 \(a_j\) 使得 \(a_j\) 不能整除 \(j\),那么我们需要使用 \(a_1\) 先将 \(a_j\) 补为 \(j\) 的倍数然后再全部移向 \(a_1\)。
AC 代码
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<algorithm>
#include<set>
#define N 100005
int n,a[N],sum,mint[N];
struct ANS{
int i,j,x;
};
struct Point{
int cos;
int val;
int pos;
};
struct cmp{
inline bool operator ()(
const Point A,
const Point B
) const {
if(A.cos!=B.cos)
return A.cos<B.cos;
return A.val>B.val;
}
};
inline void work(){
scanf("%d",&n);sum=0;
std::vector<ANS> ans;
for(register int i=1;i<=n;++i)
scanf("%d",&a[i]),sum+=a[i];
if(sum%n!=0){puts("-1");return;}
int Average=sum/n;
for(register int i=2;i<=n;++i){
int res=i-(a[i]%i);if(a[i]%i){
ans.push_back({1,i,res});
a[1]-=res,a[i]+=res;
}ans.push_back({i,1,a[i]/i});
}
for(register int i=2;i<=n;++i)
ans.push_back({1,i,Average});
printf("%d\n",ans.size());
for(auto now:ans){
printf("%d ",now.i);
printf("%d ",now.j);
printf("%d\n",now.x);
}
}
signed main(){
int T;scanf("%d",&T);
while(T--) work();
}
标签:cos,const,struct,int,题解,CF1416B,Equal,include,sum
From: https://www.cnblogs.com/UncleSamDied6/p/18010668