题目
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1972
题意
给定预算，要求各种类配件一个，品质最小最大问题
思路
如刘书思路。
有一个O(n)时间判定答案是否正确的确定性or随机判断器 + 判断算法是现代算法，随机算法，量子加密的基础，必须要掌握的思路。
感想
1. Uva 很快过了，但是UvaLA怎么也不过，后来发现是 if(mp.count(key)==0)mp[key] = mp.size();这种姿势在g++中行不通。虽然不明白是为什么，但是g++总会有各种小bug。
代码
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <tuple>
#include <set>
#include <map>
#include <cassert>
#define LOCAL_DEBUG
using namespace std;
typedef pair<int, int> MyPair;
const int MAXN = 1e3 + ;
MyPair items[MAXN][MAXN];
int itemsCnt[MAXN];
int leastPrices[MAXN][MAXN];
int budget;
int kindsNum; bool check(int quaMn) {
int remain = budget;
for (int kind_ind = ; kind_ind < kindsNum; kind_ind++) {
int cnt = itemsCnt[kind_ind];
if (quaMn > items[kind_ind][cnt - ].first)return false;
int ind = lower_bound(items[kind_ind], items[kind_ind] + cnt, MyPair(quaMn, )) - items[kind_ind];
remain -= leastPrices[kind_ind][ind];
if (remain < )return false;
}
return true;
} int search(int l, int r) {
int mid = (l + r) >> ;
if (mid == l)return l;
if (check(mid)) {
return search(mid, r);
}
else {
return search(l, mid);
}
} int main() {
#ifdef LOCAL_DEBUG
freopen("input.txt", "r", stdin);
//freopen("output2.txt", "w", stdout);
#endif // LOCAL_DEBUG
int T;
scanf("%d", &T);
for (int ti = ; ti <= T; ti++) {
memset(itemsCnt, , sizeof(itemsCnt));
map<string, int> kinds_map;
int n;
scanf("%d%d", &n, &budget);
kindsNum = ;
int min_qua = 1e9 + , max_qua = ;
for (int i = ; i < n; i++) {
char tmp[];
scanf("%s", tmp);
if (kinds_map.count(tmp) == ) {
kinds_map[tmp] = kindsNum++;
}
int kind_ind = kinds_map[tmp];
scanf("%s", tmp);
int price, qua;
scanf("%d%d", &price, &qua);
items[kind_ind][itemsCnt[kind_ind]++] = MyPair(qua, price);
min_qua = min(min_qua, qua);
max_qua = max(max_qua, qua);
}
for (int kind_ind = ; kind_ind < kindsNum; kind_ind++) {
int cnt = itemsCnt[kind_ind];
sort(items[kind_ind], items[kind_ind] + cnt);
for (int j = ; j < cnt; j++) {
leastPrices[kind_ind][j] = items[kind_ind][j].second;
}
for (int j = ; j < cnt; j++) {
if (items[kind_ind][j].first == items[kind_ind][j - ].second) {
leastPrices[kind_ind][j] = leastPrices[kind_ind][j - ];
}
}
for (int j = cnt - ; j >= ; j--) {
leastPrices[kind_ind][j] = min(leastPrices[kind_ind][j + ], leastPrices[kind_ind][j]);
}
}
int ans = search(, max_qua + );
printf("%d\n", ans);
} return ;
}