首页 > 代码库 > hdu--4974--贪心
hdu--4974--贪心
多校的题 切了5 6题 就这道会点= =
其他都是些什么树的分治 图论的一些东西= =
这题 贪心 不难发现吧 每次都尽量选取各自都能获得1分的方案 但可能会出现1 0这种只能一个人得1分 一个人得0分得的方案。
一开始 我很sb地 wa在任意选取了2人 比较他们得分大小。。
正确姿势当然是要 从大到小的来选取。 然后剩余的继续留着选取
放入个优先队列来实现比较好
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 #include <queue> 5 using namespace std; 6 7 priority_queue<int> q; 8 9 void init( )10 {11 while( !q.empty() )12 q.pop();13 }14 15 int main()16 {17 cin.sync_with_stdio(false);18 int t , n , num , ans;19 int x , y;20 cin >> t;21 for( int k = 1 ; k<=t ; k++ )22 {23 cin >> n;24 init( );25 ans = 0;26 for( int i = 1 ; i<=n ; i++ )27 {28 cin >> num;29 q.push(num);30 }31 while( !q.empty() )32 {33 x = q.top();34 if( x<=0 )35 break;36 q.pop();37 if( !q.empty() )38 {39 y = q.top();40 q.pop();41 if( y<=0 )42 {43 ans += x;44 break;45 }46 q.push( x-y );47 ans += y;48 }49 else50 {51 ans += x;52 break;53 }54 }55 cout << "Case #" << k << ": " << ans << endl;56 }57 return 0;58 }
hdu--4974--贪心
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。