//尽可能把最大利润的物品先加入,利用数组标识物品的最大利润，从而不用对p值进行排序了
#include <iostream>
#include <queue>
using namespace std;
priority_queue<int> v[10001];//v[i]表示利润p为i时插入到这个优先队列的d值
bool flag[10001];//标识可用的日期
int main()
{
	int n,i;
	while(scanf("%d",&n)!=EOF){
		int max_p=0;//用来记录整个的物品的最大值
		for(i=0;i<n;++i){
			int p,d;
			scanf("%d %d",&p,&d);
			if(p>max_p) max_p=p;
			v[p].push(d);
		}
		memset(flag,0,sizeof(flag));
		int sum=0;
		for(int t=max_p;t>0;--t){
			if(!v[t].empty()){
				while(!v[t].empty()){
					int d=v[t].top();
					v[t].pop();
					for(i=d;i>0;--i){//尽量将物品往靠近deadline的日期放
						if(!flag[i]){
							sum+=t;flag[i]=1;break;
						}
					}
					if(i==0)//如果一趟下来都没日期可用了，那么v[t]这个队列里的其余物品也没日期可用了，就可跳出这个while循环
						break;
				}
			}
		}
		cout<<sum<<endl;
	}
}

• Re:麻烦哪位牛人帮我看看这个程序，不知是思路出了问题还是细节使我没通过（附程序） (104) dizengrong 2009-04-01 16:51:02
  • Re:麻烦哪位牛人帮我看看这个程序，不知是思路出了问题还是细节使我没通过（附程序） (161) litter 2009-07-12 13:03:45