题解 P2945 【[USACO09MAR]沙堡Sand Castle】

ysy666 · 2017-08-23 09:46:14 · 题解

题目描述:

约翰用沙子建了一座城堡．正如所有城堡的城墙，这城墙也有许多枪眼，两个相邻枪眼中间那部分叫作“城齿”． 城墙上一共有N(1≤N≤25000)个城齿，每一个都有一个高度Mi.(1≤尬≤100000)．现在约翰想把城齿的高度调成某种顺序下的Bi，B2，…，BN(I≤Bi≤100000). -个城齿每提高一个单位的高度，约翰需要X(I≤X≤100)元；每降低一个单位的高度，约翰需要Y(1≤y≤100)元． 问约翰最少可用多少钱达到目的．数据保证答案不超过2^32．

解题思路：

先将修改前后的数据排一次序，比较相对应的每一位的大小，求出他们的差，然后*x或是*y

附上代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,x,y;
int a[100010],b[100010];  //两个数组分别记录初始状态和修改后的 
long long ans;  //保险起见还是用long long吧 
int main()
{
    cin>>n>>x>>y;
    for(int i=1;i<=n;i++)  cin>>a[i]>>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+=(b[i]-a[i])*x;  //如果修改前小于修改后，就让他们的差*x 
        else  ans+=(a[i]-b[i])*y;  //反之*y，相等的差为0，所以不用考虑 
    }
    cout<<ans;  //最后直接将ans输出即可 
    return 0;
}