C++(clang++ 11.0.1) 解法, 执行用时: 262ms, 内存消耗: 22920K, 提交时间: 2022-08-15 11:53:07

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <set>
using namespace std;
const int N = 3e5 + 10, inf = 1e9;
typedef long long ll;
typedef pair<int, int> PII;
int n, m;
int d[N];
vector<PII> ev, od;
set<PII> st;
void add(int a, int b, int w){
	if(a > b) swap(a, b);
	printf("%d %d %d\n",a, b, w);
	m--;
	st.insert({a, b});
}
int main(){
	scanf("%d%d", &n, &m);
    int minn = inf;
	for(int i = 1; i <= n; i++) scanf("%d", &d[i]), minn = min(minn, d[i]);
	bool flag = true;
	if(d[1] != d[n] || d[1] > minn || (1ll * n * (n - 1) / 2) < m || m < n - 1) {
		puts("No");
		return 0;
	}
	for(int i = 2; i < n; i++){
		if((d[i] - d[1]) % 2) {
			od.push_back({d[i], i});
		}else{
			ev.push_back({d[i], i});
		}
	}
	if((od.size() && !d[1]) ||(m < n - 1 + (od.size() > 0) )) {
		puts("No");
		return 0;
	}
    puts("Yes");
	add(1, n, d[1]);
	for(auto &[w, v]: ev) {
		add(1, v, (w - d[1]) / 2);
	}
	if(od.size()){
        sort(od.begin(), od.end());
        int x = od[0].first / 2, y = od[0].first / 2 + (od[0].first & 1), u = od[0].second;
        add(1, u, x), add(n, u, y);
        swap(od[0], od[od.size() - 1]);
        od.pop_back();
        for(auto &[w, v]: od) {
            add(u, v, (w - d[u]) / 2);
        }
    }
    for(int i = 1; i <= n && m > 0; i++){
        for(int j = i + 1; j <= n && m > 0; j++){
            if(!st.count({i, j})){
                add(i, j, inf);
            }
         }
    }
	return 0;
} 

C++(g++ 7.5.0) 解法, 执行用时: 218ms, 内存消耗: 28828K, 提交时间: 2022-08-13 11:43:58

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
const int N=3e5+5;
int n, m, mn=1e9+7, d[N];
vector<int> odd, even;
set<pair<int,int> > s;
bool cmp(int x,int y) { return d[x]<d[y]; }
void add(int x,int y,int z) {
	if(x>y) swap(x,y);
	printf("%lld %lld %lld\n",x,y,z);
	s.insert({x,y});
}
signed main() {
	n=read(), m=read();
	for(int i=1;i<=n;++i) {
		mn=min(d[i]=read(),mn);
		if(i>1&&i<n) {
			if((d[i]-d[1])&1) odd.push_back(i);
			else even.push_back(i);
		}
	}
	int nd=1+even.size();
	if(odd.size()) nd+=odd.size()+1;
	if(m>n*(n-1)/2||nd>m||d[1]!=d[n]||d[1]!=mn||d[n]!=mn||(!mn&&odd.size()))
		{ puts("No"); return 0; }
	puts("Yes");
	add(1,n,d[1]);
	for(auto x:even) add(1,x,(d[x]-d[1])/2);
	if(odd.size()) {
		sort(odd.begin(),odd.end(),cmp);
		int a=odd[0];
		add(1,a,d[a]/2+d[a]%2);
		add(a,n,d[a]/2);
		for(int i=1;i<odd.size();++i) {
			int b=odd[i];
			add(a,b,(d[b]-d[a])/2);
		}
	}
	m-=nd;
	for(int i=1;i<=n&&m;++i) for(int j=1;j<i;++j) {
		if(s.count({j,i})) continue;
		add(j,i,1e9);
		if(--m==0) goto end;
	}
	end:;
}