Solution

cookiebus 2023-03-31 13:48:18 13 返回题目

本题考察贪心算法,仔细读题,顺序是可以改变的,那么从贪心的角度出发考虑我们修改的对应关系应该是两个数组排序之后一一对应的。

有两个这个思路之后,我们对两个数组排个序,然后扫描一遍统计即可。

#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;
}
``
{{ vote && vote.total.up }}