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

HDU 4864 Task(貪心)

編輯:C++入門知識

HDU 4864 Task(貪心)


HDU 4864 Task

題目鏈接

題意:有一些機器和一些任務,都有時間和等級,機器能做任務的條件為時間等級都大於等於任務,並且一個任務只能被一個機器做,現在求最大能完成任務,並且保證金錢盡量多

思路:貪心,對於每個任務,時間大的優先去匹配,時間相同的,等級大的優先去匹配,因為時間占得多,時間多1就多500,而等級最多才差200。然後匹配的時候,盡量使用等級小的去匹配,而時間只要大於它的都可以用,因為是按時間優先,所以如果該時間能匹配大的,其他肯定也能匹配,那麼肯定優先匹配大的,所以只要在等級上盡量小就可以了

代碼:

#include 
#include 
#include 
using namespace std;

typedef __int64 ll;
const int N = 1444;
const int M = 105;
int n, m;
ll mac[N][M], task[N][M], used[N];

int main() {
    while (~scanf("%d%d", &n, &m)) {
	int x, y;
	memset(mac, 0, sizeof(mac));
	memset(task, 0, sizeof(task));
	memset(used, 0, sizeof(used));
	for (int i = 0; i < n; i++) {
	    scanf("%d%d", &x, &y);
	    mac[x][y]++;
	}
	for (int i = 0; i < m; i++) {
	    scanf("%d%d", &x, &y);
	    task[x][y]++;
	}
	for (int i = 0; i <= 100; i++) {
	    for (int j = 1439; j > 0; j--) {
		mac[j][i] += mac[j + 1][i];
	    }
	}
	ll num = 0;
	ll ans = 0;
	for (ll i = 1439; i > 0; i--) {
	    for (ll j = 100; j >= 0; j--) {
		if (!task[i][j]) continue;
		for (ll k = j; k <= 100; k++) {
		    if (task[i][j] > mac[i][k] - used[k]) {
			num += mac[i][k] - used[k];
			ans += (mac[i][k] - used[k]) * (i * 500 + j * 2);
			task[i][j] -= (mac[i][k] - used[k]);
			used[k] = mac[i][k];
		    }
		    else {
			num += task[i][j];
			ans += task[i][j] * (i * 500 + j * 2);
			used[k] += task[i][j];
			task[i][j] = 0;
			break;
		    }
		}
	    }
	}
	printf("%I64d %I64d\n", num, ans);
    }
    return 0;
}


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