codeforces 377B Preparing for the Contest 二分+优先队列

题目链接

给你m个bug，每个bug都有一个复杂度。n个人，每个人有两个值，一个是能力值，当能力值>=bug的复杂度时才可以修复这个bug，另一个是雇佣他需要的钱，掏一次钱就可以永久雇佣。然后给你一个金钱总额，让你在最短的时间的修复这些bugs，并且给出每个bug是由谁修复的，一个人一天只能修复一个bug。

首先，对bug的复杂度由高到低排序，对人的能力值由高到低排序。这时候需要二分修复的时间，假设需要的时间是t，那么显然，一个人一共可以修复t个bug，因为有t天。

在开始之前，先把能力值大于第一个bug的复杂度的人全都加入一个优先队列中，队列按价钱由小到大排序。然后前t个bugs都由队列首的这个人修复，之后将这个人pop。到第1+t个bug的时候，把能力值大于第二个复杂度的人全都入队列，因为人是按能力值大小排序的，所以之前在队列中的人同样可以修复第二个bug，然后不断这样循环就可以。

如果在过程中队列空了或者是价钱大于了给定的总额，就直接返回false。

在二分之前先测试一下时间为m的时候是否可行，如果不可行就直接输出no，因为这是最长的时间。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define mem(a) memset(a, 0, sizeof(a))
 4 struct node
 5 {
 6     int sk, pr, id;
 7     bool operator <(node a) const
 8     {
 9         return pr>a.pr;
10     }
11 };
12 bool cmp(node a, node b) {
13     return a.sk > b.sk;
14 }
15 const int maxn = 1e5+5;
16 int n, m, cost, ans[maxn];
17 node st[maxn], pro[maxn];
18 int check(int t) {
19     int tmpcost = cost;
20     priority_queue <node> q;
21     for(int i = 1, j = 1; j<=m; j+=t) {
22         while(i<=n&&st[i].sk>=pro[j].sk) {
23             q.push(st[i]);
24             i++;
25         }
26         if(q.empty()) {
27             return 0;
28         }
29         tmpcost -= q.top().pr;
30         for(int tmp = j; tmp<min(j+t, m+1); tmp++) {
31             ans[pro[tmp].id] = q.top().id;
32         }
33         if(tmpcost<0)
34             return 0;
35         q.pop();
36     }
37     return 1;
38 }
39 int main()
40 {
41     cin>>n>>m>>cost;
42     for(int i = 1; i<=m; i++) {
43         scanf("%d", &pro[i].sk);
44         pro[i].id = i;
45     }
46     for(int i = 1; i<=n; i++) {
47         scanf("%d", &st[i].sk);
48     }
49     for(int i = 1; i<=n; i++) {
50         scanf("%d", &st[i].pr);
51         st[i].id = i;
52     }
53     sort(pro+1, pro+1+m, cmp);
54     sort(st+1, st+1+n, cmp);
55     int flag = 0;
56     for(int i = 1; i<=n; i++) {
57         if(st[i].sk>=pro[1].sk&&st[i].pr<=cost)
58             flag = 1;
59     }
60     if(!flag) {
61         cout<<"NO"<<endl;
62         return 0;
63     }
64     int l = 1, r = m, ret;
65     while(l<=r) {
66         int mid = l+r>>1;
67         if(check(mid)) {
68             r = mid-1;
69             ret = mid;
70         }
71         else
72             l = mid+1;
73     }
74     check(r+1);
75     cout<<"YES"<<endl;
76     for(int i = 1; i<=m; i++) {
77         cout<<ans[i]<<" ";
78     }
79 }

codeforces 377B Preparing for the Contest 二分+优先队列

相关推荐