题目概述

CF1417D

解题报告

本来已经会做了，但是我把小根堆写成大根堆然后暴毙了QAQ……

我们发现 $a_1$ 可以随意向其他位置分配，因此我们考虑将其他位置都搞到 $a_1$ 上去，然后最后拿 $a_1$ 分配一下就行了。

不难想到这样的做法：用 $a_1$ 给 $a_i$ 补成 $i$ 的倍数，然后把 $a_i$ 全移到 $a_1$ 上。为了使 $a_1$ 尽量大，我们选需要补齐的量少的位置进行补齐，因此采用堆即可。

但其实根本不需要用堆……题目中保证了 $a_i>0$ ，而 $a_i$ 需要补齐的值 $<i$ ，所以刚开始 $a_2$ 一定可以被补齐，移动之后 $a_1$ 必定增大，也就是说 $a_3$ 也一定能被补齐了。以此类推，只需要按次序补齐即可。

示例程序

#include<cstdio>
#include<cctype>
using namespace std;
const int maxn=10000,maxm=30000;

int te,n,a[maxn+5],sum;
int m,L[maxm+5],R[maxm+5],X[maxm+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
void Add(int i,int j,int x){
    a[i]-=x*i;a[j]+=x*i;
    m++;L[m]=i;R[m]=j;X[m]=x;
}
int main(){
    freopen("D.in","r",stdin);freopen("D.out","w",stdout);
    for (readi(te);te;te--){
        m=0;sum=0;
        readi(n);for (int i=1;i<=n;i++) readi(a[i]),sum+=a[i];
        if (sum%n) {puts("-1");goto GG;} sum/=n;
        for (int i=2;i<=n;i++){
            int r=a[i]%i;
            if (r) Add(1,i,i-r);
            Add(i,1,a[i]/i);
        }
        for (int i=2;i<=n;i++) Add(1,i,sum);
        printf("%d\n",m);
        for (int i=1;i<=m;i++) printf("%d %d %d\n",L[i],R[i],X[i]);
        GG:continue;
    }
    return 0;
}