poj 3038

这个题我是在一个关于并查集的博客中找到的，结果我就觉得这个应该是个贪心，真想不出这个与并查集有什么鬼关系，看discuss里面也都是贪心，我是不懂大神的想法，最后，我点开链接才发现那是杭电的3038.。。我也是醉了，然后一早上就搞了这一道题。贪心还是不怎么会。

题意：就是一个牛搞了一个航空公司，想让这个航空公司可以在一天来回运送最多的客人。求最多可以运送多少客人。

思路：discuss里面有个大神说的很简单，也很有道理。

1.碰到人，上车。

2.超载，最远的乘客下车。

3.行驶到下一站。

就这三句话，解决了这个题，可我还是有点懵，感觉思路还是不是很清晰。

最后看到了一个人的博客，才最终懂了。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <queue>
 4 #include <stdlib.h>
 5 
 6 #define maxn 50005
 7 
 8 using namespace std;
 9 
10 int ans = 0,c,exist[ maxn ];
11 
12 struct note{
13     int x,y,c;
14 }to[ maxn ],ba[ maxn ];
15 
16 int cmp(const void *a,const void *b)     //排序
17 {
18     if((*(note *)a).x != (*(note * )b).x)
19         return (*(note *)a).x - (*(note * )b).x;
20     else
21         return (*(note *)a).y - (*(note * )b).y;
22 }
23 
24 void deal(note tmp[],int x)
25 {
26     priority_queue<int,vector<int>,greater<int> >small;
27     priority_queue<int,vector<int>,less<int> >most;
28     int people = 0,i;
29     memset( exist , 0 , sizeof( exist ) );
30     for( i = 0 ; i < x ; i++ )
31     {
32         small.push(tmp[i].y);
33         most.push(tmp[i].y);
34         exist[tmp[i].y] += tmp[i].c;
35         while(tmp[i].x>=small.top())    //有人到达了目的地，下车。
36         {
37             people -= exist[ small.top() ];
38             exist[ small.top() ] = 0;
39             small.pop();
40         }
41         people += tmp[ i ].c;   //上车。
42         ans += tmp[ i ].c;
43         if(people >c)     //是否超载。
44         {
45             int t = people-c;
46             ans -= t;
47             people = c;
48             while(t)
49             {
50                 if( exist[ most.top() ] > t)
51                 {
52                     exist[ most.top() ] -= t;
53                     t = 0;
54                 }
55                 else
56                 {
57                     t -= exist[ most.top() ];
58                     exist[ most.top() ] = 0;
59                     most.pop();
60                 }
61             }
62         }
63     }
64 }
65 
66 int main()
67 {
68     //freopen("in.txt","r",stdin);
69     int k,m,s,w,p,t = 0,e = 0;
70     scanf("%d%d%d",&k,&m,&c);
71     while( k-- )
72     {
73         scanf("%d%d%d",&s,&w,&p);
74         if( s < w )
75         {
76             to[ t ].x = s;
77             to[ t ].y = w;
78             to[ t++ ].c = p;
79         }
80         else
81         {
82             ba[ e ].x = w;
83             ba[ e ].y = s;
84             ba[ e++ ].c = p;
85         }
86     }
87     qsort( to , t , sizeof( to[ 0 ] ) , cmp );
88     deal( to , t );
89     qsort( ba , e , sizeof( ba[ 0 ] ) , cmp );
90     deal( ba , e );
91     printf("%d
",ans);
92     return 0;
93 }