3078800_ce.java

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <algorithm>

using namespace std;

struct node
{
	char name[21], type[21];
	int id;
	int price, quality;
}com[1001];

int n, b;
int pos[1001];

bool cmp(node a,node b)
{
	return a.price < b.price;
}

int main()
{
	int cas;
	int i, j, ID, minq, maxq, qq, bb;

	scanf("%d",&cas);
	while(cas--)
	{
		scanf("%d%d",&n,&b);
		ID = 0;
		minq = 2100000000;maxq = -1;
		for(i = 0; i < n; i++)
		{
			scanf("%s%s%d%d",com[i].type,com[i].name,&com[i].price,&com[i].quality);
			if(com[i].quality > maxq)	maxq = com[i].quality;
			if(com[i].quality < minq)	minq = com[i].quality;
		}
		for(i = 0; i < n; i++)
		{
			j = i;
			while(j < n && strcmp(com[j].type,com[i].type)==0)
			{
				com[j++].id = ID;
			}
			sort(&com[i],&com[i]+j-i,cmp);
			i = j-1;
			ID++;
		}
		for(i = 0; i < n; i++)
		{
			pos[com[i].id] = i;
		}
		pos[ID] = n;
		while(minq < maxq)
		{
			qq = (minq+maxq)/2;
			bb = 0;
			bool fail;
			
			fail = false;
			for(i = 0; i < ID&&!false; i++)
			{
				fail = true;
				for(j = pos[i]; j < pos[i+1]; j++)
				{
					if(com[j].quality >= qq)
					{
						fail = false;
						bb += com[j].price;
						break;
					}
				}
				if(bb > b)
				{
					fail = true;
				}
			}
			if(fail)
			{
				maxq = qq;
			}
			else
			{
				minq = qq+(minq==qq);
			}
		}
		printf("%d\n",minq);
	}
	return 0;
}