hdu-4864--贪心

可以很明显地知道这是个贪心但具体怎么贪心还是有点麻烦的。

先要将任务按时间T进行从大到小如果T相同则按难度从大到小排序。

机器则相反进行排序将难度从小到大进行排序如果难度相同则按T从小到大。

。。。

这边我花了很久很久去搞那个二分find()函数还是没找出错。。

后来 Porker帮我找出来了还是花了很久。。。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 typedef __int64 LL;
 7 LL n , m;
 8 LL cnt , ans;
 9 const int size = 100010;
10 bool vis[size];
11 struct data
12 {
13     int T , L;
14     bool operator < ( const data& p ) const
15     {
16         if( T==p.T )
17             return L > p.L;
18         return T > p.T;
19     }    
20 }task[size];
21 struct node
22 {
23     int T , L;
24     bool operator < ( const node& p ) const
25     {
26         if( L==p.L )
27             return T < p.T;
28         return L < p.L;
29     }
30 }mach[size];
31 
32 void init( )
33 {
34     memset( vis , false , sizeof(vis) );
35     cnt = ans = 0;
36 }
37 
38 int find( int x )
39 {
40     int L = 0 , R = n , M;
41     while( L<R )
42     {
43         M = ( L + R ) >> 1;
44         if( mach[M].L>=x )
45             R = M;
46         else
47             L = M + 1;
48     }
49     return L;
50 }    
51 
52 void solve( )
53 {
54     int pos;
55     for( int i = 0 ; i<m ; i++ )
56     {
57         pos = find( task[i].L );
58         for( int j = pos ; j<n ; j++ )
59         {
60             if( !vis[j] && mach[j].T>=task[i].T )
61             {
62                 ++ cnt;
63                 ans = ans + 1LL * 500 * task[i].T + 1LL * 2 * task[i].L;
64                 vis[j] = true;
65                 break;
66             }
67         }
68     }
69 }
70 
71 int main()
72 {
73     cin.sync_with_stdio(false);
74     while( cin >> n >> m )
75     {
76         init( );
77         for( int i = 0 ; i<n ; i++ ) //机器
78         {
79             cin >> mach[i].T >> mach[i].L;
80         }
81         for( int i = 0 ; i<m ; i++ ) //任务
82         {
83             cin >> task[i].T >> task[i].L;
84         }
85         sort( mach , mach+n );
86         sort( task , task+m );
87         solve( );
88         cout << cnt << " " << ans << endl;
89     }
90     return 0;
91 }

View Code