P2902 [USACO08MAR] Pearl Pairing G

TLE #2 #10 求调

已经很尽力了。

时间复杂度大概是$\Theta(n+n^2\log n)$

#include<bits/stdc++.h>
using namespace std;
int n,c,sum;
struct node{
	int color;
	int cnt;
	bool operator<(const node a)const{
		return cnt>a.cnt;
	}
}pearl[100005];
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
int main()
{
	n=read();
	c=read();
	sum=n;
	for(int i=1;i<=c;i++)
		pearl[i].cnt=read(),pearl[i].color=i;
	while(sum)
	{
		sort(pearl+1,pearl+c+1);
		cout<<pearl[2].color<<' '<<pearl[1].color<<endl;
		pearl[1].cnt--;
		pearl[2].cnt--;
		sum-=2;
	}
	return 0;
}