3497.cpp

PKU3497-二分加贪心,具体算法详见代码~

/*
PKU3497 ZJU3090
2009-5-9 14:38:26
二分加贪心
对质量进行二分,在同类型的配件里进行贪心 
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 1001
#define oo 1111111111

struct node {
	int quality;
	int price;
	int index;
	char type[21];
}comp[MAXSIZE];

char str[MAXSIZE][21];

int pos[MAXSIZE];
int n, money, typeCnt, minQuality, maxQuality, flag;

void calcNum() {
	int i;
	typeCnt = 0;
	memset(pos, 0, sizeof(pos));
	pos[0] = 0;
	for(i = 0; i < n - 1; ++i) {
		if(strcmp(comp[i].type, comp[i+1].type) != 0) {
			pos[++typeCnt] = i;
		}
	}
	pos[++typeCnt] = n - 1;
	//for(i = 0; i < typeCnt; ++i) {
	//	printf("pos[%d]=%d\n", i, pos[i]);
	//}
}

int cmpType(const void *a, const void *b) {
	struct node *c = (node *)a;
	struct node *d = (node *)b;
		return strcmp(c->type, d->type);
}

int cmpQuality(const void *a, const void *b) {
	struct node *c = (node *)a;
	struct node *d = (node *)b;
	if(strcmp(c->type,d->type) == 0) return c->quality > d->quality;
}

int check(int mid) {
	int i, j, k, minP, sum = 0;
	for(i = 0; i < typeCnt; ++i) {
		minP = oo;
		j = (i == 0) ? 0 : (pos[i] + 1);
		for(; j <= pos[i+1]; ++j) {
			if(mid <= comp[j].quality)
				minP = minP < comp[j].price ? minP : comp[j].price;
		}
		if(minP == oo) return 0;
		sum += minP;
	}
	if(sum > money) return 0;
	return 1;
}

int BS() {
	int mid, i, j;
	while(minQuality <= maxQuality) {
		mid = (minQuality + maxQuality) / 2;
		//printf("mid=%d\n", mid);
		if(check(mid)) {
			//printf("%d is ok\n", mid);
			minQuality = mid + 1;
			flag = 1;
		}
		else maxQuality = mid - 1;
	}
	return maxQuality;
}

int main() {
	//freopen("PKU3497.in", "r", stdin);
	//freopen("PKU3497.sol", "w", stdout);
	int i, j, k, t;
	char temp[21];
	scanf("%d", &t);
	while(t--) {
		scanf("%d%d", &n, &money);
		typeCnt = 0;
		maxQuality = -1;
		minQuality = oo;
		for(i = 0; i < n; ++i) {
			scanf("%s%s%d%d", comp[i].type, temp, &comp[i].price, &comp[i].quality);
			maxQuality = maxQuality > comp[i].quality ? maxQuality : comp[i].quality;
			minQuality = minQuality < comp[i].quality ? minQuality : comp[i].quality;
			//k = insert(comp[i].type);
			//comp[i].index = k;
			//if(k == typeCnt) {
			//	strcpy(str[k], comp[i].type);
			//	++typeCnt;
			//}
		}
		qsort(comp, n, sizeof(comp[0]), cmpType);
		qsort(comp, n, sizeof(comp[0]), cmpQuality);
		//for(i = 0; i < n; ++i) {
		//	printf("name=%s price=%d quality=%d\n", comp[i].type, comp[i].price, comp[i].quality);
		//}
		calcNum();
		flag = 0;
		i = BS();
		if(!flag) printf("0\n");
		else printf("%d\n", i);
	}
	return 0;
}