題目：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; }
