题解 | 小红的二分图构造

#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;
struct bo
{
	int xu;
	int shu;
};
bool zhao(bo a,bo b)
{
	return a.shu < b.shu;
}

int main()
{
	int m,s;cin >> m;
	vector<bo>tu(m);
	for (int i = 0;i < m;i++)
	{
		cin >> tu[i].shu;tu[i].xu = i + 1;
	}
	sort(tu.begin(), tu.end(),zhao);
		int num = 0;
		for (int i = 0;i < m;i++)
		{
			num += tu[i].shu;
		}
		if (num % 2 != 0)
		{
			cout << -1;
			return 0;
		}
		int tar = num / 2, a = 0, b = 0,zhui=0,zhao=0;
		while(b<m)
		{
			if (zhui == tar)
			{
				zhao = 1;
				break;
			}
			zhui += tu[b].shu;
			if (zhui == tar)
			{
				zhao = 1;
				break;
			}
			if (zhui < tar)b++;
			while(zhui > tar)
			{
				zhui += -tu[a].shu;
				a++;
			}
		}
		if (zhao)
		{
			vector<int>combo1;
			vector<int>combo2;
			for (int i = a;i <= b;i++)
			{
				for (int j = tu[i].shu;j > 0;j--)
					combo1.push_back(tu[i].xu);
			}
			for (int i = 0;i < a;i++)
			{
				for (int j = tu[i].shu;j > 0;j--)
					combo2.push_back(tu[i].xu);
			}
			for (int i = b+1;i <m;i++)
			{
				for (int j = tu[i].shu;j > 0;j--)
					combo2.push_back(tu[i].xu);
			}
			cout << combo1.size() << endl;
			for (int i = 0;i < combo1.size();i++)
			{
				cout << combo1[i] <<" "<< combo2[i] << endl;
			}
		}
		else cout << -1;
}