欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

D. Make Them Equal(思维+构造)

程序员文章站 2022-06-19 10:07:05
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

相关标签: 构造 思维