uva:10670 - Work Reduction（貪心）

uva:10670 - Work Reduction（貪心）

題目：10670 - Work Reduction

題目大意：給出n, m, L.n代表老板給的全部的paperworks的數量，m代表最終剩下的數量，L代表由這麼多家公司需要你來計算最小的花費。

解題思路：

1、L家公司l行。每行由公司的名字 ：A，B； A代表一份paperwork需要的money，B則代表幫你減少到總共的paperworks的數量一半要話費的money。注意這裡是你手頭上有的paperworks而不是老板要求你完成的數量，之前在這裡卡了好久。還有減半不能導致最終的數量小於m。因為老板要求的是一定要剩下m份。

2、把輸入的字符串分離出名字和錢A， B。

3、計算出金額排序輸出。

代碼：

#include 
#include 
#include 
using namespace std;

const int N = 105;
int n, m, l;
struct MONEY {

	char name[N];
	int money;
	int a, b;
} M[N];
char str[N];

int cmp (const MONEY & x, const MONEY & y) {

	if (x.money < y.money)
		return true;
	else if (x.money > y.money)
		return false;
	else return strcmp (x.name, y.name) < 0 ? true: false;
}
//分離字符串 分離出名字和費用
void handle (int j) {
	
	int k = 0;
	for (int i = 0; i < strlen (str); i++) {

		if (str[i] != ':')
			k++;
		else
			break;	
	}
	memcpy (M[j].name, str, sizeof (str));
	M[j].name[k] = '\0';
	
	int sum = 0;
	for (int i = k + 1; i < strlen (str); i++) {

		if (str[i] != ',')
			sum = sum * 10 + str[i] - '0';
		else {
			
			M[j].a = sum;
			sum = 0;
		}
	}
	M[j].b = sum;	
}
//計算費用
void cal (int j) {

	int num = n;
	int sum = 0;
	while (1) {

		if (num / 2 >= m && (num - num / 2 ) * M[j].a >= M[j].b)	{
			
			sum += M[j].b;
			num /= 2;
		} else {
			
			sum += (num - m) * M[j].a;
			M[j].money = sum;
			break;
		}
	}
}

int main () {
	
	int t;
	char ch;
	scanf ("%d", &t);
	for (int i = 1; i <= t; i++) {

		printf ("Case %d\n", i);
		scanf ("%d%d%d%c", &n, &m, &l, &ch);
		for (int j = 0; j < l ; j++) {

			gets(str);
			handle(j);
			cal(j);
		}
		sort (M, M + l, cmp);
		
		for (int j = 0; j < l ; j++)
			printf ("%s %d\n", M[j].name, M[j].money);
	}
	return 0;
}