题目大意：对n份文件进行处理使其减少到m份，有l个机构可供选择。每个机构提供两种方案：每减少一份收费a元，或者减少到文件数量的一半收费b元。根据各个机构收取费用进行排序。
很直接的题目，直接进行模拟就好了。其中对A、B两种方案的选择使用贪心策略。
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 #define MAXN 100+10 7 8 struct Agency 9 {10 char name[20];11 int cost;12 };13 Agency agency[MAXN];14 15 bool cmp (const Agency& a, const Agency& b)16 {17 if (a.cost != b.cost) return a.cost < b.cost;18 else return strcmp(a.name, b.name) < 0;19 }20 21 int main()22 {23 #ifdef LOCAL24 freopen("in", "r", stdin);25 //freopen("out", "w", stdout);26 #endif27 int T;28 scanf("%d", &T);29 for (int kase = 1; kase <= T; kase++)30 {31 int n, m, l;32 scanf("%d%d%d", &n, &m, &l);33 getchar();34 for (int i = 0; i < l; i++)35 {36 int cnt = 0;37 char ch = getchar();38 while (isupper(ch))39 {40 agency[i].name[cnt++] = ch;41 ch = getchar();42 }43 agency[i].name[cnt] = '\0';44 int a, b;45 scanf("%d,%d", &a, &b);46 getchar();47 agency[i].cost = 0;48 int remain = n;49 while (remain > m)50 {51 int half = remain / 2;52 if (half < m)53 {54 agency[i].cost += (remain - m) * a;55 remain = m;56 }57 else58 {59 int t = a * (remain - half); // the cost reducing from remain to half with A60 if (t < b) agency[i].cost += t;61 else agency[i].cost += b;62 remain = half;63 }64 }65 }66 sort(agency, agency+l, cmp);67 printf("Case %d\n", kase);68 for (int i = 0; i < l; i++)69 printf("%s %d\n", agency[i].name, agency[i].cost);70 }71 return 0;72 }
不过在读取名字的while循环中如果使用 while (ch = getchar() && isupper(ch)) 就会出问题，不知道为什么...