ACM___________________________

______________白白の屋
posts - 182, comments - 102, trackbacks - 0, articles - 0

HDOJ HDU 1789 Doing Homework again ACM 1789 IN HDU

Posted on 2010-08-04 12:03 MiYu 阅读(699) 评论(0)  编辑 收藏 引用 所属分类: ACM ( 贪心 )
//MiYu原创, 转帖请注明 : 转载自 ______________白白の屋

题目地址 :
         http://acm.hdu.edu.cn/showproblem.php?pid=1789

一道很标准的贪心题
直接贴代码:
//MiYu原创, 转帖请注明 : 转载自 ______________白白の屋

#include <iostream>
#include <algorithm>
using namespace std;
typedef struct Hm {
       int score;
       int day;      
}Hm;
bool cmp ( Hm a, Hm b )
{
     if ( a.score != b.score )
     {
         return a.score > b.score ;
     }
     else
     {
         return a.day < b.day; 
     }
}
int main()
{
    int T;
    cin >> T;
    while ( T -- )
    {
          int N;
          cin >> N;
          Hm *hm = new Hm[N];
          int flag[1001] = {0};
          for ( int i = 0; i != N ; ++ i )
          {
               cin >> hm[i].day;
          } 
          for ( int i = 0; i != N ; ++ i )
          {
               cin >> hm[i].score;
          }
          sort ( hm, hm + N, cmp );
          int total = 0;
          for ( int i = 0; i != N; ++ i )
          {
               int j;
               for ( j = hm[i].day; j != 0; -- j )
               {
                    if ( !flag[j] )
                    {
                        flag[j] = 1;
                        break; 
                    } 
               } 
               if ( !j )
               {
                    total += hm[i].score; 
               }
          }
          cout << total << endl;
          delete [] hm;
    }
    return 0; 
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理