Assemble---UVALive组装电脑-3971---二分数组

Time limit 3000 ms

题目链接https://vjudge.net/contest/305270#problem/L

题目大意：给你t组数据，给你n个配件各自的种类、名称、价格、品质要求每个种类都要买一个总价格不超过b元，且品质最差配件的品质因子应尽量大。求最大的品质最差配件因子。其中价格为不超过106的非负整数，品质为不超过109的非负整数。

这题可以直接看出来是个二分。。。我们对品质最差的品质因子二分就好了，剔除掉所有品质因子小于mid的，剩下的取每种的最小价格就好了：

int ok(int x) 
{
	map<string, int>q;
	int sum = 0;
	for (int i=1; i<=n; i++) {
		if (a[i].quilt < x) continue;
		if (!q[a[i].type]) {
			q[a[i].type] = a[i].price;
			sum += a[i].price;
		}
		else {
			if (a[i].price<q[a[i].type]) {
				sum -= q[a[i].type];
				sum += a[i].price;
				q[a[i].type] = a[i].price;
			}
		}
	}
	for (int i = 1; i <= n; i++) if (!q[a[i].type]) return 0;//判断是否每种都有
	if (sum > limt) return 0;
	return 1;
}
           

其中limt就是你拥有的钱。

emmm，二分过程完美，

以下是WA了代码（之后有解释—你能看出来吗？）：

#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <cstring>
#include <algorithm>
using namespace std;
const int mac = 1000 + 10;
int n, limt;
struct node {
	string type, name;
	int price, quilt;
} a[mac];
int qual[mac];
int ok(int x);
int main() {
	int t;
	cin >> t;
	while (t--) {
		cin >> n >> limt;
		int ma = 0,num=0;
		for (int i=1; i<=n; i++) {
			cin >> a[i].type >>a[i].name >>a[i].price >>a[i].quilt;
			qual[++num]=a[i].quilt;
			ma = max(ma, a[i].quilt);
		}
		sort(qual+1,qual+1+n);
		int l = 1, r = n, mid,ans=0;
		for (int i=1; i<=32; i++) {
			mid = (l + r) >> 1;
			if (ok(qual[mid])) {//对qual数组二分，确保得到的值在已出现的范围内
				ans = qual[mid];
				l = mid + 1;
			} else r = mid - 1;
		}
		cout << ans << endl;
	}
	return 0;
}
int ok(int x) 
{
	map<string, int>q;
	int sum = 0;
	for (int i=1; i<=n; i++) {
		if (a[i].quilt < x) continue;
		if (!q[a[i].type]) {
			q[a[i].type] = a[i].price;
			sum += a[i].price;
		} 
		else {
			if (a[i].price<q[a[i].type]) {
				sum -= q[a[i].type];
				sum += a[i].price;
				q[a[i].type] = a[i].price;
			}
		}
	}
	for (int i = 1; i <= n; i++) if (!q[a[i].type]) return 0;
	if (sum > limt) return 0;
	return 1;
}
           

emmm，本题用map有一个巨大的坑点。。。而且题目中也隐藏着一个坑点。。。就是价格可能等于0。。。蒟蒻的我就因为这个WA了5发QAQ。。。当价格=0的时候使用!q[a[i].price]就是找死啊。。。。我们把它为零的值直接改成-1就好了，接下来就特判一下是不是为-1就好了。。。

以下是AC代码：

#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <cstring>
#include <algorithm>
using namespace std;
const int mac = 2000 + 10;
int n, limt;
struct node {
	string type, name;
	int price, quilt;
} a[mac];
int qual[mac];
int ok(int x);
int main() {
	int t;
	cin >> t;
	while (t--) {
		cin >> n >> limt;
		for (int i=1; i<=n; i++) {
			cin >> a[i].type >>a[i].name >>a[i].price >>a[i].quilt;
			if (a[i].price==0) a[i].price=-1;
			qual[i]=a[i].quilt;
		}
		sort(qual+1,qual+1+n);
		int l = 1, r = n, mid,ans=0;
		for (int i=1; i<=32; i++) {
			mid = (l + r) >> 1;
			if (ok(qual[mid])) {
				ans = qual[mid];
				l = mid + 1;
			} else r = mid - 1;
		}
		cout << ans << endl;
	}
	return 0;
}
int ok(int x) {
	map<string, int>q;
	int sum = 0;
	for (int i=1; i<=n; i++) {
		if (a[i].quilt < x) continue;
		if (q[a[i].type]==0) {
			q[a[i].type] = a[i].price;
			if (a[i].price!=-1)
				sum += a[i].price;
		} 
		else {
			if (a[i].price<q[a[i].type]) {
				sum -= q[a[i].type];
				if (a[i].price!=-1) sum += a[i].price;
				q[a[i].type] = a[i].price;
			}
		}
	}
	for (int i = 1; i <= n; i++) if (q[a[i].type]==0) return 0;
	if (sum > limt) return 0;
	return 1;
}