CoinStacks

The first line of input contains an integer n (2 ≤ n ≤ 50), the number of coin stacks. Then follows a line containing n nonnegative integers a1, a2, . . . , an, where ai is the number of coins in the i’th stack. The total number of coins is at most 1000.

If the players can win the game, output a line containing “yes”, followed by a description of the moves. Otherwise output a line containing “no”. When describing the moves, output one move per line, each move being described by two distinct integers a and b (between 1 and n) indicating that the players remove a coin from stacks a and b. If there are several possible solutions, output any one of them.

Python3 解法, 执行用时: 66ms, 内存消耗: 7040K, 提交时间: 2021-08-03 15:06:53

n=int(input())
l=[int(i) for i in input().split()]
fl=[]
for i in range(n):
	if(l[i]==0):
		continue;
	fl.append([i+1,l[i]])
if(sum(l)%2==1):
	print("no")
else:
	op=[]
	op.append("yes")
	while fl!=[]:
		if(len(fl)==1):
			break
		fl=sorted(fl,key=lambda x:x[1])
		op.append("{} {}".format(str(fl[0][0]),str(fl[-1][0])))
		fl[0][1]-=1
		if(fl[0][1]==0):
			fl.pop(0)
		fl[-1][1]-=1
		if(fl[-1][1]==0):
			fl.pop(-1)
	if(fl==[]):
		for i in op:
			print(i)
	else:
		print("no")

C++ 解法, 执行用时: 4ms, 内存消耗: 436K, 提交时间: 2021-08-06 12:56:31

#include<bits/stdc++.h>
using namespace std;
int n, a, cnt;
string ans = "yes\n";
pair<int, int>pii[55]; 
signed main()
{
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		cin >> a;
		if(a)
			pii[cnt++] = {-a, i};
	}
	while(1)
	{
		sort(pii, pii+cnt);
		for(; cnt && !pii[cnt-1].first; cnt--);
		if(cnt == 1)
			return !puts("no");
		if(!cnt)
			break;
		++pii[0].first, ++pii[1].first;
		ans += to_string(pii[0].second) + " " + to_string(pii[1].second) +"\n";
	}
	cout << ans;
}

详情