hdu 4544 湫湫系列故事—

hdu 4544 湫湫系列故事——消灭兔子

http://acm.hdu.edu.cn/showproblem.php?pid=4544
优先队列+贪心。
 1 #include <cstdio>
 2 #include <queue>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 #define ll long long
 7 #define maxn 1000010
 8 using namespace std;
 9 
10 int b[maxn];
11 struct node
12 {
13     int d;
14     int p;
15     bool operator <(const node &a)const
16     {
17         return d<a.d;
18     }
19 }pp[maxn];
20 
21 int n,m;
22 
23 int main()
24 {
25     while(scanf("%d%d",&n,&m)!=EOF)
26     {
27         priority_queue<int,vector<int>,greater<int> >q;
28         for(int i=0; i<n; i++)
29         {
30             scanf("%d",&b[i]);
31         }
32         for(int i=0; i<m; i++)
33         {
34             scanf("%d",&pp[i].d);
35         }
36         for(int i=0; i<m; i++)
37         {
38             scanf("%d",&pp[i].p);
39         }
40         sort(b,b+n);
41         sort(pp,pp+m);
42         int pos=m-1;
43         ll ans=0;
44         bool flag=true;
45         for(int i=n-1; i>=0; i--)
46         {
47             while(pos>=0&&pp[pos].d>=b[i])
48             {
49                 q.push(pp[pos].p);
50                 pos--;
51             }
52             if(q.empty())
53             {
54                 flag=false;
55                 break;
56             }
57             ans+=q.top();
58             q.pop();
59         }
60         if(flag) cout<<ans<<endl;
61         else printf("No
");
62     }
63     return 0;
64 }
View Code