D. Make Them Equal 思维构造

2024-04-13 13:38

文章标签 思维构造 make equal

本文主要是介绍D. Make Them Equal 思维构造，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

题意

您将得到一个由𝑛个正整数组成的数组array，从1到number编号。您最多可以执行3次以下操作：

选择三个整数𝑖，𝑗和𝑥（1≤𝑖，𝑗≤𝑛;0≤𝑥≤109）;
分配𝑎𝑖：= 𝑎𝑖−𝑥⋅𝑖，𝑎𝑗：=𝑎𝑗𝑥⋅𝑖。
每次操作后，数组的所有元素都应为非负数。

您能找到不超过3个运算的序列，之后数组的所有元素都相等吗？

分析

很显然，处理完之后的合法数组每个数字就是数组和的平均数，题目最后还说明不要求操作次数最少，所以我们可以选择一个比较合适的过渡点

如果我们选择i为1的话，那么根据选择的x的不同，𝑥⋅𝑖可以包含所有整数，也就是说此时我们无论选择哪一个j，都可以保证有对应的x，使得操作完之后aj的值为平均值。
而题目要求每次操作完之后数组每一项都为非负数，所以我们可以提前预处理一下，把所有值都转移到a1上，再由a1进行分配

代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstring>
#include <map>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define x first 
#define y second
#define _CRT_SECURE_NO_WARNINGS
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC option("arch=native","tune=native","no-zero-upper")
#pragma GCC target("avx2")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
struct xxx{int a,b,c;
};
const int INF = 0x3f3f3f3f;
const int N = 1e4 + 10;
int a[N];
vector<xxx> ans;
int n;int main(){int T;scanf("%d",&T);while(T--){ans.clear();scanf("%d",&n);int sum = 0;for(int i = 1;i <= n;i++){scanf("%d",&a[i]);sum = sum + a[i];}if(sum % n != 0){puts("-1");continue;}int avg = sum / n;for(int i = 2;i <= n;i++){if(a[i] % i != 0){int t = a[i] % i;t = i - t;a[i] += t;ans.push_back({1,i,t});}ans.push_back({i,1,a[i] / i});}for(int i = 2;i <= n;i++) ans.push_back({1,i,avg});printf("%d\n",(int)ans.size());for(auto t:ans) printf("%d %d %d\n",t.a,t.b,t.c);}return 0;
}