做法是计算m+1个区间放1头和2头牛的贡献,但仅过了第1个点,计算哪里出问题了呢?
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define int long long
using namespace std;
const int N=2e5+5;
struct grass{
int p;
int t;
};
grass g[N];
priority_queue<pair<int,int> > pq;
int pp[N],tt[N],f[N],one[N],two[N],mk[N],k,m,n,ans,pt;
bool cmp(grass u,grass v){return u.p<v.p;}
int qsum(int l,int r){//区间[l,r)
int lb=lower_bound(pp+1,pp+k+1,l)-pp;
int rb=lower_bound(pp+1,pp+k+1,r)-pp-1;
return tt[rb]-tt[lb-1];
}
signed main(){
cin>>k>>m>>n;
for(int i=1;i<=k;i++)cin>>g[i].p>>g[i].t;
for(int i=1;i<=m;i++)cin>>f[i];
sort(g+1,g+k+1,cmp);
sort(f+1,f+m+1);//排序
for(int i=1;i<=k;i++)pp[i]=g[i].p,tt[i]=g[i].t;
for(int i=1;i<=k;i++)tt[i]+=tt[i-1];
one[0]=two[0]=tt[upper_bound(pp+1,pp+k+1,f[1])-pp-1];
one[m]=two[m]=tt[k]-tt[lower_bound(pp+1,pp+k+1,f[m])-pp-1];
for(int i=1;i<m;i++)two[i]=qsum(f[i],f[i+1]);
//for(int i=0;i<=m;i++)cout<<two[i]<<' ';
for(int i=1;i<m;i++){
while(pp[pt]<f[i]&&pt<=k)pt++;
while(pp[pt]<=(f[i]+f[i+1])/2&&pt<=k){
one[i]=max(one[i],qsum(pp[pt],pp[pt]+(f[i+1]-f[i])/2));
pt++;
}
}
for(int i=0;i<=m;i++)pq.push({one[i],i});
for(int i=1;i<=n;i++){
pair<int,int> pr=pq.top();
pq.pop();
ans+=pr.first;
mk[pr.second]++;
if(mk[pr.second]==1)pq.push({two[pr.second]-one[pr.second],pr.second});
}
cout<<ans;
return 0;
}