4pts求调
查看原帖
4pts求调
797769
manbaOUT楼主2025/8/1 12:23

做法是计算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;
}
2025/8/1 12:23
加载中...