SnowWolf's Wine Shop

题目链接：https://vjudge.net/problem/HDU-1897

思路

在multiset面前，这题就是个模拟，是给multiset量身定做的题，哈哈。因为multiset插入和删除都是logN,然后还可以放入重复元素。所以对于每一个需求，只需要lower_bound一下就可以了。

坑点

auto it = st.lower_bound(cur); 用自带的没问题
auto it = lower_bound(st.begin(),st.end(),cur);用普通版的就会超时

代码

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int T,N,Q,Y;
int A[maxn],B[maxn];
multiset<int> st;

void solve(){
    for(int i = 1;i<=Q;i++){
        int cur  = B[i];
        auto it = st.lower_bound(cur);
        //auto it = lower_bound(st.begin(),st.end(),cur);
        if(it == st.end() || *it > cur + Y) puts("-1");
        else {
            printf("%d\n",*it);
            st.erase(it);
        }
    }
}

int main(){
    scanf("%d",&T);
    int kase = 0;
    while(T--){
        printf("Case %d:\n",++kase);
        st.clear();
        scanf("%d %d %d",&N,&Q,&Y);
        for(int i = 1;i<=N;i++) {
            int cur;scanf("%d",&cur);
            st.insert(cur);
        }
        for(int i = 1;i<=Q;i++) scanf("%d",&B[i]);
        solve();
    }
    return 0;
}