寻宝.cpp

来自「有关算法设计与分析的几个小程序（查找与替换问题、炒饭问题、寻宝问题等）」· C++ 代码 · 共 33 行

#include <iostream>
using namespace std;
long a[1001];
int main()
{
	int t,n,i,v,p;
	long vt,vp;
	scanf("%d",&t);
	while(t--)
    {
		scanf("%d%d",&n,&vt);
		vp=0;
		memset(a,0,sizeof(a));
		for(i=0;i<n;i++)
		{
			scanf("%d%d",&v,&p);
			a[p]+=v;
		}
		for(i=1000;i>0;i--)
			if(a[i]<=vt)
			{
				vp=vp+i*a[i];
				vt-=a[i];
			}
			else
				break;
			vp=vp+vt*i;
			printf("%ld\n",vp);
	}
	return 0;
}