死亡

【问题描述】

　　现在有M个位置可以打sif,有N+1个人在排队等着打sif。现在告诉你前N个人每个人需要多长的时间打sif，问你第N+1个人什么时候才能打sif。（前N个人必须按照顺序来）

【输入格式】

　　第一行两个整数N，M如上所述。

　　接下来N行每行一个整数代表每个人所需要用的时间。

【输出格式】

　　一行一个整数表示答案

【样例输入】

　　3  2

　　1

　　1

　　1

【样例输出】

　　1

【样例解释】

　　山里有座庙。

【数据规模与约定】

　　对于100%的数据，每个人所需用的时间不超过10^5.

【题目分析】

　　首先这个我们很容易看出来第一个测试点输出N个数中的最小值就可以了。

　　好吧，不扯了，说一下正解。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#define ll long long
using namespace std;
int n,m;
int a[100010];
priority_queue<ll>heap;
int main()
{
    freopen("death.in","r",stdin);
    freopen("death.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)//先给m个位置加入元素 
        heap.push(0);
    for(int i=1;i<=n;i++)
    {
        ll now=heap.top();//先把最大的元素取出来，实际上是最小的，因为取了他的负数 
        heap.pop();//删掉 
        now=-now;//把负数变为正数 
        now+=a[i];//加上新元素的时间来打sif 
        now=-now;//变为负数 
        heap.push(now);//加入堆中 
    }
    long long ans=1e17+10;
    for(int i=1;i<=m;i++)
    {
        ans=min(ans,-heap.top());//heap中都是负数，所以这里比较时先变为正数 
        heap.pop();
    }
    cout<<ans;
    fclose(stdin);fclose(stdout);
    return 0;
}