题目描述

Farmer John has built a sand castle! Like all good castles, the walls have crennelations, that nifty pattern of embrasures (gaps) and merlons (filled spaces); see the diagram below. The N (1 <= N <= 25,000) merlons of his castle wall are conveniently numbered 1..N; merlon i has height Mi (1 <= Mi <= 100,000); his merlons often have varying heights, unlike so many.
He wishes to modify the castle design in the following fashion: he has a list of numbers B1 through BN (1 <= Bi <= 100,000), and wants to change the merlon heights to those heights B1, ..., BN in some order (not necessarily the order given or any other order derived from the data).
To do this, he has hired some bovine craftsmen to raise and lower the merlons' heights. Craftsmen, of course, cost a lot of money. In particular, they charge FJ a total X (1 <= X <= 100) money per unit height added and Y (1 <= Y <= 100) money per unit height reduced.
FJ would like to know the cheapest possible cost of modifying his sand castle if he picks the best permutation of heights. The answer is guaranteed to fit within a 32-bit signed integer.
Note: about 40% of the test data will have N <= 9, and about 60% will have N <= 18.

输入描述:

* Line 1: Three space-separated integers: N, X, and Y
* Lines 2..N+1: Line i+1 contains the two space-separated integers: Mi and Bi

输出描述:

* Line 1: A single integer, the minimum cost needed to rebuild the castle

示例1

输入
3 6 5 
3 1 
1 2 
1 2 
输出
11
说明
FJ's castle starts with heights of 3, 1, and 1. He would like to change them so that their heights are 1, 2, and 2, in some order. It costs 6 to add a unit of height and 5 to remove a unit of height.
FJ reduces the first merlon's height by 1, for a cost of 5 (yielding merlons of heights 2, 1, and 1). He then adds one unit of height to the second merlon for a cost of 6 (yielding merlons of heights 2, 2, and 1).

解答

这题看到有dalao用优先队列做，其实用数组做也比较方便（主要是刚学的新手好理解）

读入数据，再调用快排函数，对号入座，最后输出

一道经典贪心，话不多说，上代码！ 

#include<cstdio>
#include<iostream>
#include<algorithm>//万能头文件，sort必备
using namespace std;
long long ans;//其实题目上说2^31-1，不会爆int，但开long long保险一点
int a[1000005],b[1000005];//数组开大点，不会错（只要不爆）
int main(){//过程华丽开始
    int n,x,y;
    cin>>n>>x>>y;//读入
    for(int i=1;i<=n;i++){//读入
        cin>>a[i];
        cin>>b[i];
    }
    sort(a+1,a+1+n);//直接快排，用贪心做
    sort(b+1,b+1+n);
    for(int i=1;i<=n;i++){//开始处理（贪心）
        if(a[i]>b[i])ans+=(a[i]-b[i])*y;//如果高就下降
        if(a[i]<b[i])ans+=(b[i]-a[i])*x;//如果低就上升
        //这里其实省了一步等于的情况，其实要不要无所谓，等于本来就不加不减QAQ
       }
    printf("%lld\n",ans);//输出，记得用long long就对号入座用%lld，用int就%d
    return 0;//过程华丽结束
}