BestCoder#91Lotus and Characters

Lotus有$n$种字母，给出每种字母的价值以及每种字母的个数限制，她想构造一个任意长度的串。
定义串的价值为：第1位字母的价值*1+第2位字母的价值*2+第3位字母的价值*3……
求Lotus能构造出的串的最大价值。（可以构造空串，因此答案肯定$\ge 0$）

第一行是数据组数$T(0\le T\le 1000)$。
对于每组数据，第一行一个整数$n(1\le n\le 26)$，接下来$n$行，每行2个整数val_i,cnt_i(|val_i|,cnt_i\leq 100)val?i??,cnt?i??(∣val?i??∣,cnt?i??≤100)，分别表示第$i$种字母的价值和个数限制。

对于每组数据，输出一行一个整数，表示答案。

2
2
5 1
6 2
3
-5 3
2 1
1 1

35
5

出题人分析：

根据排序不等式，显然应该把字母从小往大放。 一种错误的做法是把正权值的字母取出来从前往后放。错误是因为负权的也可能出现在答案中：放在最前面来使后面每个字母的贡献都增加。 正确的做法是把字母从大往小从后往前放，如果加入该字母后答案变小就停下来。

收获：代码细节有进制转换的原理，有收获！

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 30;
struct chr
{int val, cnt;bool operator < (const chr &other) const{return val < other.val;}
}a[maxn];
int main()
{int T, n;scanf("%d", &T);while(T--){scanf("%d", &n);for(int i = 1; i <= n; i++)scanf("%d%d", &a[i].val, &a[i].cnt);sort(a+1, a+n+1);int sum = 0, ans = 0;while(n){sum += a[n].val;if(sum < 0)break;ans += sum;a[n].cnt--;if(!a[n].cnt)n--;}cout << ans << endl;}return 0;
}