题目大意：对n份文件进行处理使其减少到m份，有l个机构可供选择。每个机构提供两种方案：每减少一份收费a元，或者减少到文件数量的一半收费b元。根据各个机构收取费用进行排序。
很直接的题目，直接进行模拟就好了。其中对A、B两种方案的选择使用贪心策略。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 100+10 struct Agency
{
char name[];
int cost;
};
Agency agency[MAXN]; bool cmp (const Agency& a, const Agency& b)
{
if (a.cost != b.cost) return a.cost < b.cost;
else return strcmp(a.name, b.name) < ;
} int main()
{
#ifdef LOCAL
freopen("in", "r", stdin);
//freopen("out", "w", stdout);
#endif
int T;
scanf("%d", &T);
for (int kase = ; kase <= T; kase++)
{
int n, m, l;
scanf("%d%d%d", &n, &m, &l);
getchar();
for (int i = ; i < l; i++)
{
int cnt = ;
char ch = getchar();
while (isupper(ch))
{
agency[i].name[cnt++] = ch;
ch = getchar();
}
agency[i].name[cnt] = '\0';
int a, b;
scanf("%d,%d", &a, &b);
getchar();
agency[i].cost = ;
int remain = n;
while (remain > m)
{
int half = remain / ;
if (half < m)
{
agency[i].cost += (remain - m) * a;
remain = m;
}
else
{
int t = a * (remain - half); // the cost reducing from remain to half with A
if (t < b) agency[i].cost += t;
else agency[i].cost += b;
remain = half;
}
}
}
sort(agency, agency+l, cmp);
printf("Case %d\n", kase);
for (int i = ; i < l; i++)
printf("%s %d\n", agency[i].name, agency[i].cost);
}
return ;
}
不过在读取名字的while循环中如果使用 while (ch = getchar() && isupper(ch)) 就会出问题，不知道为什么...