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

uva 10670 Work Reduction (貪心)

編輯:C++入門知識

uva 10670 Work Reduction (貪心)


uva 10670 Work Reduction


Paperwork is beginning to pile up on your desk, and tensions at the workplace are starting to mount. Your boss has threatened to fire you if you don't make any progress by the end of the day. You currently have N units of paperwork on your desk, and your boss demands that you have exactly M units of paperwork left by the end of the day.

The only hope for you now is to hire help. There are various agencies which offer paperwork reduction plans:

For $A they will reduce your paperwork by one unit.
For $B they will reduce your entire paperwork by half (rounding down when necessary).

Note that work can never be reduced to less than 0.

Your task now is to produce a sorted table of agency names and their respective minimum costs to solve your workload problem.

The first line of input consists of a single positive integer representing the number of cases to follow. Each case begins with three positive integers separated by spaces: N - your starting workload, M - your target workload, and L - the number of work reduction agencies available to you, (1 <= M <= N <= 100000, 1 <= L <= 100). The next L lines have the format "[agency name]:A,B", where A and B are the rates as described above for the given agency. (0 <= A,B <= 10000) The length of the agency name will be between 1 and 16, and will consist only of capital letters. Agency names will be unique.

For each test case, print "Case X", with X being the case number, on a single line, followed by the table of agency names and their respective minimum costs, sorted in non-decreasing order of minimum costs. Sort job agencies with identical minimum costs in alphabetical order by agency name. For each line of the table, print out the agency name, followed by a space, followed by the minimum required cost for that agency to solve your problem.

Sample Input

2
100 5 3
A:1,10
B:2,5
C:3,1
1123 1122 5
B:50,300
A:1,1000
C:10,10
D:1,50
E:0,0

Sample Output

Case 1
C 7
B 22
A 37
Case 2
E 0
A 1
D 1
C 10
B 50


題目大意:每組數據包括兩個部分:

1)N總任務數,M目標任務數,L公司數目。

2)L行,每行3個有效數據:編號(長度1~16),完成一個任務所需的金額,完成一般任務所需的金額(一半為 (當前任務數 + 1) / 2)。

求每家公司完成N - M個任務所需的最小金額,按金額的升序輸出,若金額相同,按字符序輸出。

解題思路:貪心。先減半,減半到不能再減(再減小於M),或者減半的性價比不如減一時,開始減一。



#include
#include
#include
#include
using namespace std;
int N, M, L;
char s[10000];
struct A{
	char id[20];
	int a, b, sum;
};
A f[10500];
int cmp(A p, A q) {
	if (p.sum != q.sum) {
		return p.sum < q.sum;
	}
	else return strcmp(p.id, q.id) < 0;
}
void cal(int x) {
	f[x].sum = 0;
	int temp = N;
	while (temp - (temp + 1) / 2 >= M && f[x].b < (temp + 1) / 2 * f[x].a) {
		temp -= (temp + 1) / 2;
		f[x].sum += f[x].b;
	}
	f[x].sum += f[x].a * (temp - M);
}
int main() {
	int T, Case = 1;
	scanf("%d", &T);
	while (T--) {
		printf("Case %d\n", Case++);
		scanf("%d %d %d\n", &N, &M, &L);
		for (int i = 0; i < L; i++) {
			scanf("%s", s);
			for (int j = 0; j < strlen(s); j++) {
				if (s[j] == ':') {
					s[j] = ' ';
					break;
				}
			}
			sscanf(s, "%s%d,%d\n", f[i].id, &f[i].a, &f[i].b);
			cal(i);
		}
		sort(f, f + L, cmp);
		for (int i = 0; i < L; i++) {
			printf("%s %d\n", f[i].id, f[i].sum);
		}
	}
	return 0;
}



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