hdu 6011 Lotus and Characters 贪心

http://acm.hdu.edu.cn/showproblem.php?pid=6011

先把数字从小到大排好，比如是-6、3、4这样，

然后处理出后缀和，当后缀和 <= 0的时候马上停止就好了。

证明：

假如现在是去到了第二个，也就是那个3，后缀和是7，那么我选不选-6呢？

如果选，

结果是: 1 * (-6) + 2 * 3 + 3 * 4

        = 1 * (-6) + 3 + 4 + [1 * 3 + 2 * 4]

此时后缀和 > 0，对答案是有贡献的。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;


#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
const int maxn = 1e2 + 20;
struct node {
    int val, cnt;
    bool operator < (const struct node & rhs) const {
        if (val != rhs.val) return val < rhs.val;
        else return 0;
    }
}a[maxn];
vector<int>haha;
int last[222222];
void work() {
    int n;
    scanf("%d", &n);
    int mx = -inf;
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &a[i].val, &a[i].cnt);
        mx = max(mx, a[i].val);
    }
    sort(a + 1, a + 1 + n);
    haha.push_back(-inf);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= a[i].cnt; ++j) {
            haha.push_back(a[i].val);
        }
    }
    int sum = 0, pos = inf;
    for (int i = haha.size() - 1; i >= 0; --i) {
        sum += haha[i];
        if (sum <= 0) {
            pos = i + 1;
            break;
        }
    }
    LL ans = 0;
    int now = 1;
    for (int i = pos; i < haha.size(); ++i) {
        ans += now * haha[i];
        now++;
    }
    cout << ans << endl;
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    int t;
    scanf("%d", &t);
    while (t--) work();
    return 0;
}