51nod 第二场II人行横道航运中心

Question

有 n 件行李（编号 1 到 n ）以及 m 个箱子（编号 1 到 m ）。第 i 件行李的大小为 w[i] ，价值为 v[i] 。每个箱子只可以装一件行李，并且尺寸不能超过 x[i] 。

因为某种原因，箱子有时会变得不可用，有 q 个询问。每个查询给出两个整数 l 和 r ，即从 l 到 r 号箱子不可用，请你回答，在这种情况下，剩余的箱子最多能够放下多少价值的行李。

输入
第一行：3个数n,m,q，中间用空格分隔。
后面n行，每行2个数，对应n个箱子的 w[i] 和 v[i]。
之后一行共有m个数，表示箱子的容量。
之后q行，每行两个数 l,r 对应不可用箱子的范围。
其中1≤n,m,q≤50，1≤w[i],v[i],x[i]≤1000000。
输出
输出q行。每行一个询问的答案。
数据范围
对于100%的数据，1≤n,m,q≤50,1≤w[i],v[i],x[i]≤1000000,l≤r≤m。

输入样例
3 4 3
1 9
5 3
7 8
1 8 6 9
4 4
1 4
1 3
输出样例
20
0
9

Answer 1

#include <bits/stdc++.h>
#define int long long
#define PI pair<int,int>
using namespace std;
const int maxm=2e6+5;
PI e[maxm];
PI ee[maxm];
int n,m,q;
void solve(){
cin>>n>>m>>q;
for(int i=1;i<=n;i++){
int x,y;cin>>x>>y;
e[i]={x,y};
}
for(int i=1;i<=m;i++){
int x;cin>>x;
ee[i]={x,i};
}
sort(e+1,e+1+n);
sort(ee+1,ee+1+m);
while(q--){
int l,r;cin>>l>>r;
priority_queue<int,vector,less >q;
int ans=0;
int j=1;
for(int i=1;i<=m;i++){
if(ee[i].second>=l&&ee[i].second<=r)continue;
while(j<=n&&e[j].first<=ee[i].first){
q.push(e[j].second);
j++;
}
if(q.size()){
ans+=q.top();q.pop();
}
}
cout<<ans<<endl;
}
}
signed main(){
ios::sync_with_stdio(0);
solve();
return 0;
}