首页 > 代码库 > POJ3614 Sunscreen 【贪心】
POJ3614 Sunscreen 【贪心】
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 4204 | Accepted: 1458 |
Description
To avoid unsightly burns while tanning, each of the C (1 ≤ C ≤ 2500) cows must cover her hide with sunscreen when they‘re at the beach. Cow i has a minimum and maximum SPF rating (1 ≤ minSPFi ≤ 1,000; minSPFi≤ maxSPFi ≤ 1,000) that will work. If the SPF rating is too low, the cow suffers sunburn; if the SPF rating is too high, the cow doesn‘t tan at all........
The cows have a picnic basket with L (1 ≤ L ≤ 2500) bottles of sunscreen lotion, each bottle i with an SPF rating SPFi (1 ≤ SPFi ≤ 1,000). Lotion bottle i can cover coveri cows with lotion. A cow may lotion from only one bottle.
What is the maximum number of cows that can protect themselves while tanning given the available lotions?
Input
* Line 1: Two space-separated integers: C and L
* Lines 2..C+1: Line i describes cow i‘s lotion requires with two integers: minSPFi and maxSPFi
* Lines C+2..C+L+1: Line i+C+1 describes a sunscreen lotion bottle i with space-separated integers: SPFi and coveri
Output
A single line with an integer that is the maximum number of cows that can be protected while tanning
Sample Input
3 2 3 10 2 5 1 5 6 2 4 1
Sample Output
2
Source
贪心解法:将牛和防晒霜分别按照first值升序排序,然后对于每个防晒霜,将起点<=它的位置的牛都放入优先队列里,然后从优先队列里取出右端值最小的合法牛加入ans。0ms。
#include <stdio.h> #include <string.h> #include <queue> #include <algorithm> #include <iostream> #define maxn 2510 using namespace std; struct Node { int first, second; friend bool operator<(const Node& a, const Node& b) { return a.second > b.second; } } cow[maxn], sun[maxn]; bool cmp(const Node& a, const Node& b) { return a.first < b.first; } int main() { int C, L, i, j, ans = 0; Node tmp; scanf("%d%d", &C, &L); for(i = 0; i < C; ++i) scanf("%d%d", &cow[i].first, &cow[i].second); for(i = 0; i < L; ++i) scanf("%d%d", &sun[i].first, &sun[i].second); sort(cow, cow + C, cmp); sort(sun, sun + L, cmp); priority_queue<Node> PQ; for(i = j = 0; i < L; ++i) { while(j < C) { if(cow[j].first > sun[i].first) break; PQ.push(cow[j++]); } while(!PQ.empty() && sun[i].second) { tmp = PQ.top(); if(tmp.second < sun[i].first) PQ.pop(); else if(tmp.first <= sun[i].first) { --sun[i].second; ++ans; PQ.pop(); } } } printf("%d\n", ans); return 0; }
网络流解法:比赛时用这个代码险过,900多ms。
#include <stdio.h> #include <string.h> #define maxn 4010 #define maxm maxn * 2000 #define inf 0x3f3f3f3f int head[maxn], id, N, L, source, sink; struct Node { int u, v, c, next; } E[maxm]; void addEdge(int u, int v, int c) { E[id].u = u; E[id].v = v; E[id].c = c; E[id].next = head[u]; head[u] = id++; E[id].u = v; E[id].v = u; E[id].c = 0; E[id].next = head[v]; head[v] = id++; } void getMap() { memset(head, -1, sizeof(head)); int i, j, a, b; source = 3502; sink = source + 1; for(i = 0; i < N; ++i) { addEdge(source, i, 1); scanf("%d%d", &a, &b); for(j = a; j <= b; ++j) addEdge(i, j + N, 1); } while(L--) { scanf("%d%d", &a, &b); addEdge(N + a, sink, b); } } int dep[maxn], ps[maxn], cur[maxn]; int Dinic(int n, int s, int t) { int tr, res = 0; int i, j, k, f, r, top; while(true) { memset(dep, -1, n * sizeof(int)); for(f = dep[ps[0] = s] = 0, r = 1; f != r; ) for(i = ps[f++], j = head[i]; j != -1; j = E[j].next) { if(E[j].c && -1 == dep[k=E[j].v]) { dep[k] = dep[i] + 1; ps[r++] = k; if(k == t) { f = r; break; } } } if(-1 == dep[t]) break; memcpy(cur, head, n * sizeof(int)); for(i = s, top = 0; ; ) { if(i == t) { for(k = 0, tr = inf; k < top; ++k) if(E[ps[k]].c < tr) tr = E[ps[f=k]].c; for(k = 0; k < top; ++k) E[ps[k]].c -= tr, E[ps[k]^1].c += tr; res += tr; i = E[ps[top = f]].u; } for(j = cur[i]; cur[i] != -1;j = cur[i] = E[cur[i]].next) if(E[j].c && dep[i] + 1 == dep[E[j].v]) break; if(cur[i] != -1) { ps[top++] = cur[i]; i = E[cur[i]].v; } else { if(0 == top) break; dep[i] = -1; i = E[ps[--top]].u; } } } return res; } int main() { // freopen("stdin.txt", "r", stdin); scanf("%d%d", &N, &L); getMap(); printf("%d\n", Dinic(sink + 1, source, sink)); return 0; }
POJ3614 Sunscreen 【贪心】