装进肚子

链接

本题的数据量很大,穷举所有可能几乎不可能 n<=100000 //胖不死你

可以采用数学方法

设早上吃的糖果的甜蜜度为am={}

晚上吃的糖果的甜蜜度为pm={}

我们可以计算am-pm的值,并从大到小排序,最大的肯定就是早上该吃的,也就是说,

前k个取排序后的函数早上吃的,后面取晚上吃的

如果这样算还是好麻烦

我计算得到的差值为kam-kpm

我想要kam+(n-k)pm

不难发现,只需要令差值加上晚上吃的糖果的甜蜜度总和就得到求答案了

am,pm只是为了形象讲解而设出来的,实际上我们可以优化掉,但时间应该差不多,

空间倒是有一定优化

代码实现

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    long long sum=0;
    vector<int>dif;
    for(int i=0;i<n;i++){
        int num;cin>>num;
        dif.push_back(num);
    }
    for(int i=0;i<n;i++){
        int num;cin>>num;
        sum+=num;
        dif[i]-=num;
    }
    sort(dif.begin(),dif.end(),greater<int>());
    for(int i=0;i<k;i++){
        sum+=dif[i];
    }
    cout<<sum;
}

时间复杂度:O(n log n)排序占主导地位

空间复杂度:O(n)