D. Make Them Equal(思维+构造)
程序员文章站
2022-03-26 11:40:34
https://codeforces.com/contest/1417/problem/D思路:观察一下样例可以知道能构造出来的最后会变成平均值。想着题目3*n,所以可以考虑扫三次序列。最后一次应该是把通过一个数把全部数字变成平均数。那么前两次应该是收集到一个数字上。构造想着方便那么用i==1去构造,但是发现题目的ai只能是减,ai减到负数之类的就不好搞了。所以要尝试把后面的数都加到ai。但是直接加没法加。要使得a1加的话后面只能是减,发现后面的数要减完只能是i的倍数。所以第一次要把i=2~n全...
https://codeforces.com/contest/1417/problem/D
思路:观察一下样例可以知道能构造出来的最后会变成平均值。
想着题目3*n,所以可以考虑扫三次序列。最后一次应该是把通过一个数把全部数字变成平均数。那么前两次应该是收集到一个数字上。
构造想着方便那么用i==1去构造,但是发现题目的ai只能是减,ai减到负数之类的就不好搞了。所以要尝试把后面的数都加到ai。但是直接加没法加。要使得a1加的话后面只能是减,发现后面的数要减完只能是i的倍数。所以第一次要把i=2~n全部变成i的倍数,这个理论上是可以成立的。(虽然不是很懂要怎么去证明)。第一次之后再把后面的数都放到a1去。最后由a1平均分配。
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e5+100;
typedef long long LL;
LL a[maxn];
void oper(LL i,LL j,LL x)
{
a[i]-=i*x;
a[j]+=i*x;
cout<<i<<" "<<j<<" "<<x<<endl;
}
void solve()
{
LL n;cin>>n;LL sum=0;
for(LL i=1;i<=n;i++) cin>>a[i],sum+=a[i];
if(sum%n) {
cout<<"-1"<<endl;return;
}
cout<<3*(n-1)<<endl;
for(LL i=2;i<=n;i++)
{
oper(1,i,(i-a[i]%i)%i);
oper(i,1,a[i]/i);
}
for(LL i=2;i<=n;i++)
{
oper(1,i,sum/n);
}
}
int main(void)
{
cin.tie(0);std::ios::sync_with_stdio(false);
LL t;cin>>t;
while(t--)
{
solve();
}
return 0;
}
本文地址:https://blog.csdn.net/zstuyyyyccccbbbb/article/details/108855687
上一篇: 装饰者模式和观察者模式