首页 > 代码库 > hdu-4864--贪心

hdu-4864--贪心

2024-08-08 14:08:27   215人阅读

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

先要将 任务按时间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 data12 {13     int T , L;14     bool operator < ( const data& p ) const15     {16         if( T==p.T )17             return L > p.L;18         return T > p.T;19     }    20 }task[size];21 struct node22 {23     int T , L;24     bool operator < ( const node& p ) const25     {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         else47             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

 

hdu-4864--贪心


联系
我们