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;
}