蓝桥杯刷题 前缀和与差分-[3142]可获得的最小取值（C++）

问题描述

妮妮学姐手头有一个长度为n的数组a，她想进行次操作来取出数组中的元素。每次操作必须选择以

下两种操作之一:

取出数组中的最大元素

取出数组中的最小元素和次小元素

妮妮学姐希望在进行完 次操作后，取出的数的和最小。她感觉有些困难，于是请擅长贪心的你帮

助她解决这个问题。

输入格式

第一行输入两个整数n和，表示数组长度和操作次数

第二行输入n个整数表示数组a。

数据范围保证3<n<2x 105，1< ai< 109，1k < 99999，2k <n。

输出格式

样例输入

5
2 5 1 10 6

样例输出

3

知识点：前缀和与差分

代码 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200020;
ll a[N],b[N],sum=LLONG_MAX;
int main()
{
	ll n,k,temp=0;
  cin>>n>>k;
  for(int i=1;i<=n;i++)
  {
    cin>>a[i];
  }
  sort(a,a+n+1);
  for(int i=1;i<=n;i++)
  {
    b[i]=b[i-1]+a[i];
  }
  for(int p=0;p<=k;p++)
  {
    temp=b[2*p]+b[n]-b[n+p-k];
    sum=min(sum,temp);
  }
  cout<<sum<<endl;
	return 0;
}