题目描述
给定一个长度为 N 的序列 A,要求把该序列分成若干段,在满足“每段中所有数的和”不超过M的前提下,让“每段中所有数的最大值”之和最小。试计算这个最小值。
样例
输入格式
第一行包含两个整数 N和 M。
第二行包含 N个整数,表示完整的序列 A。
输出格式
输出一个整数,表示结果。
如果结果不存在,则输出 −1。
数据范围
0≤N≤10^5,
0≤M≤10^11,
序列A中的数非负,且不超过10^6
输入样例:
8 17
2 2 2 8 1 8 2 1
输出样例:
12
算法1
代码其实不长,但优先队列前后相关的数据都要入队列,即q[k]和q[k+1]
调试时间挺长的,才发现这一点。
关键点:单调队列中有两个数才把结果加入优先队列,优先队列也必须把这两个数附上,所以优先队列存的是pair<long long,pair<int,int>>
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef pair<long long,pair<int,int>> PLII;
const int N=100010;
int n,a[N],q[N];
long long m,dp[N];
bool del[N];
priority_queue<PLII,vector<PLII>,greater<PLII>> qu;
int main(){
scanf("%d%lld",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]>m) return puts("-1")&0;
}
int hh=0,tt=0;
long long sum=0;
for(int i=1,j=0;i<=n;i++){
sum+=a[i];
while(sum>m) sum-=a[++j];
while(hh<=tt && q[hh]<j) del[q[hh]]=true,hh++;
while(hh<=tt && a[q[tt]]<=a[i]) del[q[tt]]=true,tt--;
q[++tt]=i;
if(hh<tt) qu.push({dp[q[tt-1]]+a[q[tt]],{q[tt-1],q[tt]}});
dp[i]=dp[j]+a[q[hh]];
while(qu.size()) {
auto t=qu.top().second;
if(!del[t.first] && !del[t.second]) break;
qu.pop();
}
if(qu.size()) dp[i]=min(dp[i],qu.top().first);
}
printf("%lld\n",dp[n]);
return 0;
}
算法2
用multiset也挺方便,还不用处理前后相关的数据,即q[k]和q[k+1]
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int a[N],c[N],q[N],n;
long long m,f[N],sum;
multiset<long long> s;
int main(){
cin>>n>>m;
for(int i=1,j=0;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]>m) return puts("-1") & 0;
sum+=a[i];
while(sum>m)sum-=a[j+1],j++; //(j,i]满足sum<=main
c[i]=j;
}
int hh=1, tt=0; //开始队列为空
for(int i=1;i<=n;i++){
while(hh<=tt && q[hh] <= c[i]){
if(hh<tt) s.erase(f[q[hh]]+a[q[hh+1]]); //这样更清晰,
hh++; //不加if也没关系,因为erase不存在的不会有副作用
}
while(hh<=tt && a[q[tt]]<=a[i]){
if(hh<tt) s.erase(f[q[tt-1]]+a[q[tt]]);
tt--;
}
if(hh<=tt) s.insert(f[q[tt]]+a[i]); //队列中有,才插入s
q[++tt]=i;
f[i]=f[c[i]]+a[q[hh]];//q[hh]=0时不影响结果
if(s.size()) f[i]=min(f[i],*s.begin());
}
cout<<f[n]<<endl;
}
大佬, if(hh<tt) qu.push({dp[q[tt-1]]+a[q[tt]],{q[tt-1],q[tt]}});
这行的push 里边没搞明白,求指点😭