题目：今天有N个任务需要处理，下班前需要剩下M个任务未完成，有很多代理公司可以帮忙，
他们分别有两种业务，完成1个任务需要花费A，完成剩余工作的一般需要花费B，
如果全都让代理公司处理，求每个代理公司的最小花费。
分析：贪心。每次将余下的一半当做一个整体，判断那种花费小即可。
如果剩余奇数个任务，代理公司会处理掉整除/2 + 1个。
说明：开始用DP处理，结果TLE了。
#include <stdio.h> #include <stdlib.h> #include <string.h> char buf[101][128], name[101][128]; int id[101], ans[101]; int cmp(const void *a, const void *b) { if (ans[*(int *)a] == ans[*(int *)b]) { return strcmp(name[*(int *)a], name[*(int *)b]); }else { return ans[*(int *)a] - ans[*(int *)b]; } } int deal(int N, int M, int A, int B) { if (N == M) { return 0; } if (N/2 >= M) { int v = (N-N/2) * A; if (v > B) { v = B; } return deal(N/2, M, A, B) + v; } return deal(N - 1, M, A, B) + A; } int main() { int T, N, M, L, A, B; scanf("%d",&T); for (int t = 1; t <= T; ++ t) { scanf("%d%d%d",&N,&M,&L); printf("Case %d\n",t); for (int i = 0; i < L; ++ i) { scanf("%s",buf[i]); id[i] = i; } for (int i = 0; i < L; ++ i) { for (int j = 0; buf[i][j]; ++ j) { if (buf[i][j] == ':') { buf[i][j] = ' '; break; } } sscanf(buf[i], "%s %d,%d", name[i], &A, &B); ans[i] = deal(N, M, A, B); } qsort(id, L, sizeof(int), cmp); for (int i = 0; i < L; ++ i) { printf("%s %d\n", name[id[i]], ans[id[i]]); } } return 0; }