Wannafly挑战赛12 B T95要减肥 【贪心】

链接：https://www.nowcoder.com/acm/contest/79/B

来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 262144K，其他语言524288K

64bit IO Format: %lld

题目描述

T95提速啦，然而她觉得自己还是太慢了！

于是T95决定减肥——然而T95还喜欢吃麦当劳

现在有n种赛道，n家麦当劳，第i条赛道的痛苦值是ai，第i家麦当劳的快乐值是bi

为了减肥，T95吃的麦当劳次数不能大于她跑步的次数

由于T95太重了，每个赛道跑一次之后就会坏掉

由于T95喜欢吃不同的口味，每家麦当劳最多吃一次

由于明斯克航空航天局的蜜汁bug，T95每跑3次就会得到额外的m块乐值

现在T95想知道她可以得到的最大（快乐值的和-痛苦值的和）是多少

输入描述:

第一行两个数n,m

第二行n个数表示ai

第三行n个数表示bi

输出描述:

输出一行一个数表示答案

示例1

输入

5 10

0 1 3 6 8

0 4 5 6 6

输出

23

说明

样例解释：

跑：1,0,3

吃：6,5,6

额外：10

备注:

对于100%的数据，有1 <= n <= 1000000 , 0<=ai,bi,m<=2000000000

思路

先将痛苦值 从小到大 排序

再将快乐值 从大到小 排序

然后模拟这个过程

找出这个过程中的最大值 就是答案

AC代码

#include <cstdio>

#include <cstring>

#include <ctype.h>

#include <cstdlib>

#include <cmath>

#include <climits>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <map>

#include <stack>

#include <set>

#include <numeric>

#include <sstream>

#include <iomanip>

#include <limits>

#define CLR(a) memset(a, 0, sizeof(a))

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

typedef pair<string, int> psi;

typedef pair<string, string> pss;

const double PI = 3.14159265358979323846264338327;

const double E = exp(1);

const double eps = 1e-6;

const int INF = 0x3f3f3f3f;

const int maxn = 1e6 + 5;

const int MOD = 1e9 + 7;

int a[maxn], b[maxn];

bool comp(int x, int y)

{

    return x > y;

}

int main()

{

    int n, m;

    cin >> n >> m;

    for (int i = 0; i < n; i++)

        scanf("%d", &a[i]);

    for (int i = 0; i < n; i++)

        scanf("%d", &b[i]);

    sort(a, a + n);

    sort(b, b + n, comp);

    ll ans = 0, temp = 0;

    for (int i = 0; i < n; i++)

    {

        if ((i + 1) % 3 == 0)

            temp += m;

        temp += (b[i] - a[i]);

        ans = max(temp, ans);

    }

    cout << ans << endl;

}