书法网站建站目标,网络安装公司,做外贸网站特色,网站源码下载问题描述
妮妮学姐手头有一个长度为 nn 的数组 aa#xff0c;她想进行 kk 次操作来取出数组中的元素。每次操作必须选择以下两种操作之一#xff1a;
取出数组中的最大元素。取出数组中的最小元素和次小元素。
妮妮学姐希望在进行完 kk 次操作后#xff0c;取出的数的和最…问题描述
妮妮学姐手头有一个长度为 nn 的数组 aa她想进行 kk 次操作来取出数组中的元素。每次操作必须选择以下两种操作之一
取出数组中的最大元素。取出数组中的最小元素和次小元素。
妮妮学姐希望在进行完 kk 次操作后取出的数的和最小。她感觉有些困难于是请擅长贪心的你帮助她解决这个问题。
输入格式
第一行输入两个整数 nn 和 kk 表示数组长度和操作次数。
第二行输入 nn 个整数表示数组 aa 。
数据范围保证 3≤n≤2×1051≤ai≤1091≤k≤999992kn3≤n≤2×1051≤ai≤1091≤k≤999992kn 。
输出格式
样例输入
5 1
2 5 1 10 6样例输出
3#include iostream
#includevector
#include algorithm
#include climits // 用于 INT_MAX 或 LLONG_MAX
using namespace std;
//贪心不对每次在操作1和操作2中选较小的值。
//例如{3, 1, 1, 1, 1, 1, 1}做k3次操作每次都按贪心法
//做3次操作2结果是6。但是正确答案是做3次操作1结果是5。
//设操作2做p次操作1做k-p次:anssum[2p]sum[n]-sum[np-k],尝试所有可能的p
int main()
{int n,k;cinnk;//不是n,kvectorint a(n1,0);vectorlong long sum(n1,0);for(int i1;in;i){cina[i];}sort(a.begin()1,a.end());//对1-n进行排序//!!!!!!a和sum要分开写sum的计算要在排序之后for(int i1;in;i){sum[i]sum[i-1]a[i];}long long ansLLONG_MAX;//存疑for(int p1;pk;p){ansmin(ans,sum[2*p]sum[n]-sum[n-kp]);//不是2p}coutans;return 0;
} 说明
对于样例我们通过操作 22 取出 11 和 22 可以获得最小值。
