codeforce每日一题链接

题目描述

给定一个长度为n的数组和k，请选出k个数字，顺序与原数组的顺序一致。将它分成前后两部分，使得两部分的最大值最小。

样例

输入样例1

6
5 4
1 10 1 1 1
5 3
1 20 5 15 3
5 3
1 20 3 15 5
10 6
10 8 20 14 3 8 6 4 16 11
10 5
9 9 2 13 15 19 4 9 13 12
1 1
1

输出样例1

2
6
5
21
18
1

算法

(二分+堆) $O(n*log(n))$

答案是有范围的，所以我们可以二分答案。我们在判断mid是否可行时，$left[i]$数组表示，从0到i在选择的数字不超过mid的情况下，最多能选择多少数字，right就表示从右选择，从i到n-1在选择的数字不超过mid的情况下，最多能选择多少数字。然后我们可以枚举分界点，如果两边最多能选取的数字数量大于k的话，返回true。

C++ 代码

#include<bits/stdc++.h>

#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
#define SZ(a) (int)a.size()

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;

const int N = 2e5+10, M = N * 2, INF = 0x3f3f3f3f, mod = 1e9 + 7;

int n, m;

bool check(LL mid, vector<int> w)
{
    vector<int> left(n+1, 0);
    vector<int> right(n+1, 0);
    priority_queue<int> heap1;
    LL sum = 0;
    for(int i=0;i<n;i++)
    {
        heap1.push(w[i]);
        sum += w[i];
        while(sum>mid && heap1.size()){
            sum -= heap1.top();
            heap1.pop();
        }
        left[i]=heap1.size();
    }
    sum = 0;
    priority_queue<int> heap2;
    for(int i=n-1;~i;i--)
    {
        sum += w[i];
        heap2.push(w[i]);
        while(sum>mid && heap2.size())
        {
            sum -= heap2.top();
            heap2.pop();
        }
        right[i] = heap2.size();
    }

    int res = 0;
    for(int i=-1;i<n;i++){
        if(i==-1) res = max(res, right[i+1]);
        else if(i==n-1) res=max(res, left[i]);
        else res=max(res, left[i]+right[i+1]);
    }
    return res >= m;
}

void solve()
{
    cin>>n>>m;
    vector<int> w(n+1, 0);
    for(int i=0;i<n;i++) cin>>w[i];
    LL l=0,r=3e14;
    while(l<r)
    {
        LL mid=l+r>>1;
        if(check(mid, w)) r=mid;
        else l=mid+1;
    }
    cout<<r<<endl;
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }

    return 0;
}