51nod 1689

51nod 1689

原题链接

每次枚举逛街的终点，终点确定则在路上的花费便确定，接下来处理逛店的花费。

用1号大根堆保存经过的花费最小的K个c=1的店，用2号大根堆保存可以逛的其他的店，再用3号大根堆保存剩余的店。花费则是1号堆的花费加上2号的花费。

每次路过新店，判断能否加入1号堆，否则扔进2号堆，调整2号和3号使2号堆保存花费不超过T的其他店，3号堆保存剩余暂不能逛的店。

#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<fstream>
#include <iostream>
#include<algorithm>
#define debug puts("ssssssssssss")
#define ll long long
#define MP make_pair
#define mm(a,b) memset(a,b,sizeof(a))
#define rep(a,b) for(int a=1;a<=b;a++)
#define e 2.7182818284590452354
using namespace std;
const int MOD=100000007;
const int maxb=500+10;
const int MAXN=100005;
const int maxn=1005;
const double eps=1e-10;
int n, k;
ll T;
priority_queue<int> Q1,Q2,Q3;
int a[MAXN], b[MAXN], c[MAXN];
int main(){
//    ifstream fin(&#");
//    ofstream fout(&#");ll sum1, sum2;int ans;cin>>n>>T>>k;rep(i,n) cin>>a[i];rep(i,n) cin>>b[i];rep(i,n) cin>>c[i];sum1=sum2=0;ans=-1;for(int i=1;i<=n;i++){if(c[i]){if(Q1.size()<k){Q1.push(b[i]);sum1+=b[i];}else{Q1.push(b[i]);sum1+=b[i];Q2.p());sum2+&#p();sum1-&#p();Q1.pop();}}else{Q2.push(b[i]);sum2+=b[i];}if(Q1.size()<k) continue;if(sum1+a[i]>T) continue;ll temp=T-sum1-a[i];while(!Q3.empty()&&!Q2.empty()&&-Q3.top()&p()){int reg&#p();sum2-&#p(), sum2-&#p();Q2.pop(), Q2.push(-Q3.top());Q3.pop(), Q3.push(-reg);}while(!Q3.empty()&&temp>&#p()){Q2.push(-Q3.top()), sum2-&#p();Q3.pop();}while(!Q2.empty()&&temp<sum2){Q3.push(-Q2.top()), sum2-&#p();Q2.pop();}if(temp>=sum2&&k+(int)Q2.size()>ans){ans=k+(int)Q2.size();}}cout<<ans<<endl;return 0;
}