LA3971-Assemble（贪心+二分）

题目链接：

http://acm.hust.edu.cn/vjudge/problem/13338

思路：

使最小值最大，只需要对目标进行二分，并且judge一下是否合法，在judge函数里面，用贪心思想，对于满足条件的，选择价值最低的

代码

#include <iostream> #include <cstring> #include <stack> #include <vector> #include <set> #include <map> #include <cmath> #include <queue> #include <sstream> #include <iomanip> #include <fstream> #include <cstdio> #include <cstdlib> #include <climits> #include <deque> #include <bitset> #include <algorithm> using namespace std; #define PI acos(-1.0) #define LL long long #define PII pair<int, int> #define PLL pair<LL, LL> #define mp make_pair #define IN freopen("in.txt", "r", stdin) #define OUT freopen("out.txt", "wb", stdout) #define scan(x) scanf("%d", &x) #define scan2(x, y) scanf("%d%d", &x, &y) #define scan3(x, y, z) scanf("%d%d%d", &x, &y, &z) #define sqr(x) (x) * (x) #define pr(x) cout << #x << " = " << x << endl #define lc o << 1 #define rc o << 1 | 1 #define pl() cout << endl const int maxn = 1000 + 5; const int maxq = 1000000000; int n, bg, cnt; map<string, int> id; vector<PII> v[maxn]; int getid(string s) { if (!id.count(s)) id[s] = cnt++; return id[s]; } bool judge(int x) { int mon = 0; for (int i = 0; i < cnt; i++) { int t = bg + 1; int _s = v[i].size(); for (int j = 0; j < _s; j++) { if (v[i][j].second >= x) t = min(t, v[i][j].first); } if (t == bg + 1) return false; mon += t; if (mon > bg) return false; } return true; } void init() { id.clear(); for (int i = 0; i <= n; i++) v[i].clear(); } int main() { int x, y, T; scan(T); while (T--) { cnt = 0; scan2(n, bg); init(); for (int i = 0; i < n; i++) { char s1[30], s2[30]; scanf("%s %s %d %d", s1, s2, &x, &y); v[getid(s1)].push_back(mp(x, y)); } int L = 0, R = maxq, M; while (L < R) { M = L + (R - L + 1) / 2; if (judge(M)) L = M; else R = M - 1; } printf("%d\n", L); } return 0; }