ACM模版

描述

题解

把W[i]当做X[i]点的个数，也就是说把一个权值为W[i]的X[i]点转化为W[i]个X[i]点，然后对X[i]排序，最后前后配对儿相减即可。

这里需要强调的是要避免数据溢出，这一点坑了我半个小时之久……
因为自己定义的P[a].P和power均为int型，所以在匹配的过程中，出现了int * int溢出的情况，我还傻傻的将其赋值给了long long型的sum，却忽略了——这里本身就存在溢出的漏洞……o(>﹏<)o千万别再这么粗心了！都是想当然惹的祸。

代码

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 1e4 + 10;

struct point
{
    int P;
    int power;
} P[MAXN];

bool cmp(point a, point b)
{
    return a.P < b.P;
}

int main(int argc, const char * argv[])
{
    int N;
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        cin >> P[i].P >> P[i].power;
    }
    sort(P, P + N, cmp);

    long long sum = 0;
    int flag = N - 1;
    long long power;
    for (int i = 0; i < flag;)
    {
        power = P[flag].power > P[i].power ? P[i].power : P[flag].power;
        sum += (P[flag].P - P[i].P) * power;    // BUG 防止int * int溢出，所以power定义为long long
        P[flag].power -= power;
        P[i].power -= power;
        if (!(P[flag].power))
        {
            flag--;
        }
        if (!(P[i].power))
        {
            i++;
        }
    }

    std::cout << sum << '\n';
    return 0;
}

参考

51Nod 1108 距离之和最小 V2