前缀和（例题）

lanqiao OJ3142

问题描述

妮妮学姐手头有一个长度为 nn 的数组 aa，她想进行 kk 次操作来取出数组中的元素。每次操作必须选择以下两种操作之一：

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

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

输入格式

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

第二行输入 nn 个整数表示数组 aa 。

数据范围保证 3≤n≤2×105，1≤ai≤109，1≤k≤99999，2k<n3≤n≤2×105，1≤ai​≤109，1≤k≤99999，2k<n 。

输出格式

样例输入

5 1
2 5 1 10 6

样例输出

3

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n ,k;
const int N =200010;
ll a[N],sum[N]; 
int main(){
  cin>>n>>k;
  for(int i=1;i<=n;i++){
    cin>>a[i];
  }
  sort(a+1,a+n+1);
  for(int i=1;i<=n;i++){
    sum[i] =sum[i-1]+a[i]; 
  }
  ll ans = 1e18;
  for(int i=1;i<=k;i++){
    ans = min(sum[n]-sum[n+i-k]+sum[2*i],ans);
  }

  cout<<ans;

  return 0;
}

 P1811 - [NewOJ Week 5] 并行处理 - New Online Judge

题目描述

现在有n个任务需要到GPU上跑，但是只有两张GPU，每张GPU一次只能运行一个任务，两个GPU可以并行处理。
告诉你n个任务需要的时间，你需要选择一个数字i：
将任务1到任务i放到第一个GPU上运行，任务i+1到任务n放到第二个GPU上运行。
请你求出最短运行时间。

输入格式

输入第一行为正整数n，1≤n≤100000。
第二行为n个整数Ai，表示第i个任务需要的时间，1≤Ai≤10^9。

输出格式

输出一个数字表示答案。

输入样例 复制

3
4 2 3

输出样例 复制

5

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100010;
ll sum[N];
int n;
int main(){
  cin>>n;
  for(int i=1;i<=n;i++){
    int a;
    cin>>a;
    sum[i]=sum[i-1]+a;
  }
  ll ans =sum[n];
  for(int i=1;i<=n;i++){
    ans = min(ans,max(sum[i],sum[n]-sum[i]));
  }
  cout<<ans<<endl;
  return 0;
}