程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 貪心-hdu-1789-Doing Homework again

貪心-hdu-1789-Doing Homework again

編輯:C++入門知識

題目意思:
有n個作業,每個作業有一個截止日期,每個作業如果超過截止日期完成的時候有一個懲罰值,問怎樣安排作業,使懲罰值最小。

解題思路:

貪心。

先按懲罰值從大到小排序,懲罰值越大,就應該盡量安排改作業在截止日期之前完成,而怎樣保證既在截止日期之前完成,又保證其他的作業的懲罰值總和較小呢,應該安排在離該截止日期最近的可安排那個日期,這樣就保證了懲罰值最小。

代碼:

<SPAN style="FONT-SIZE: 18px">#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/
struct Inf
{
   int pun,dl;
}inf[1100];
bool vis[1100];

bool cmp(struct Inf a,struct Inf b)
{
  if(a.pun!=b.pun) //按懲罰值從大到小排序
     return a.pun>b.pun;
  return a.dl<b.dl;  //懲罰值相同的話,截止日期靠前的先安排
}

int main()
{
   int n,t;

   scanf("%d",&t);
   while(t--)
   {
      scanf("%d",&n);
      for(int i=1;i<=n;i++)
         scanf("%d",&inf[i].dl);
      for(int i=1;i<=n;i++)
         scanf("%d",&inf[i].pun);

      sort(inf+1,inf+n+1,cmp);
      memset(vis,false,sizeof(vis));
      int ans=0;
      for(int i=1;i<=n;i++)
      {
         int t=inf[i].dl,j;
         for(j=t;j>=1;j--) //找到最靠近的那天,
         {
            if(!vis[j])
            {
               vis[j]=true;
               break;
            }
         }
         if(j<1) //如果前面都放了,只能接受懲罰,此時的懲罰值是比較小的
            ans+=inf[i].pun;
      }
      printf("%d\n",ans);

   }
   return 0;
}
</SPAN>

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved