程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 4864 Task(2014 Multi-University Training Contest 1) 貪心算法,hdu4864

HDU 4864 Task(2014 Multi-University Training Contest 1) 貪心算法,hdu4864

編輯:C++入門知識

HDU 4864 Task(2014 Multi-University Training Contest 1) 貪心算法,hdu4864


題目鏈接:Task

Task

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 893    Accepted Submission(s): 201


Problem Description Today the company has m tasks to complete. The ith task need xi minutes to complete. Meanwhile, this task has a difficulty level yi. The machine whose level below this task’s level yi cannot complete this task. If the company completes this task, they will get (500*xi+2*yi) dollars.
The company has n machines. Each machine has a maximum working time and a level. If the time for the task is more than the maximum working time of the machine, the machine can not complete this task. Each machine can only complete a task one day. Each task can only be completed by one machine.
The company hopes to maximize the number of the tasks which they can complete today. If there are multiple solutions, they hopes to make the money maximum.  

 

Input The input contains several test cases. 
The first line contains two integers N and M. N is the number of the machines.M is the number of tasks(1 < =N <= 100000,1<=M<=100000).
The following N lines each contains two integers xi(0<xi<1440),yi(0=<yi<=100).xi is the maximum time the machine can work.yi is the level of the machine.
The following M lines each contains two integers xi(0<xi<1440),yi(0=<yi<=100).xi is the time we need to complete the task.yi is the level of the task.  

 

Output For each test case, output two integers, the maximum number of the tasks which the company can complete today and the money they will get.  

 

Sample Input 1 2 100 3 100 2 100 1  

 

Sample Output 1 50004  

 

Source 2014 Multi-University Training Contest 1  

題意:

有n個機器,m個任務。每個機器至多能完成一個任務。對於每個機器,有一個最大運行時間xi和等級yi,對於每個任務,也有一個運行時間xj和等級yj。只有當xi>=xj且yi>=yj的時候,機器i才能完成任務j,並獲得500*xj+2*yj金錢。問最多能完成幾個任務,當出現多種情況時,輸出獲得金錢最多的情況。

分析:

  從一開頭就知道了貪心的基本思路。就是先將任務和機器按降序排列(先時間,時間相同再按難度),然後采用貪心求解。當時腦洞太大,先選擇機器,再選擇該機器能完成的最大利潤的任務,但是選擇下一個機器的時候,忘了考慮被上一個機器忽略的那些任務,導致無限WA,到最後才想到有這一茬。網上給的題解是先選任務然後再選適合的最小機器。按照題解稍微修改了自己的代碼然後AC了,其實和先選機器的思想是一致的,唉,太水無能。

代碼:

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 #define maxn 100010
 8 struct node{
 9     int tm, dif;
10 }MCH[maxn], TSK[maxn];
11 
12 bool cmp(node a, node b)
13 {
14     if(a.tm==b.tm) return a.dif > b.dif;
15     return a.tm > b.tm;
16 }
17 int main()
18 {
19     int n, m;
20     while(~scanf("%d%d", &n, &m))
21     {
22         for(int i = 1; i <= n; i++)
23             scanf("%d%d", &MCH[i].tm, &MCH[i].dif);
24         for(int i = 1; i <= m; i++)
25             scanf("%d%d", &TSK[i].tm, &TSK[i].dif);
26         sort(MCH+1, MCH+n+1, cmp);
27         sort(TSK+1, TSK+m+1, cmp);
28         int cnt = 0, c[102];
29         __int64 sum = 0;
30         memset(c, 0, sizeof(c));
31         for(int i = 1, j = 1; i <= m; i++)
32         {
33             while(j <= n && MCH[j].tm >= TSK[i].tm)
34             {
35                 c[MCH[j].dif]++;
36                 j++;
37             }
38             for(int k = TSK[i].dif; k <= 100; k++)
39             {
40                 if(c[k])
41                 {
42                     cnt++;
43                     c[k]--;
44                     sum += 500*TSK[i].tm+2*TSK[i].dif;
45                     break;
46                 }
47             }
48         }
49         printf("%d %I64d\n", cnt, sum);
50     }
51     return 0;
52 }

 

   

2013 Multi-University Contest 2 HDU 4611 Balls Rearrangement測試數據死活我的過不了

www.cnblogs.com/...1.html
看看這個網站,博主有QQ,可以請教呀。
 

大牛幫忙解決一下,hdu 2820 Permutaion http://acmhdueducn/showproblemphp?pid=2820

打表吧,0秒過的應該是用這個方法,偶猜想可能用自動機做
 

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