51nod 1191 消灭兔子

51nod的题都好恶心,这个题一开始我想的是把b[i]放里面然后枚举每个箭找能杀死的兔子,因为lower是找兔子里面大于等于这个箭的.我一开始想把迭代器--然后找.最后一直没调过,发现只需要把伤害和兔子的血量变为负值,就可以直接二分了在对钱和伤害排序的时候,因为我要把价格从小到大,然后箭的攻击从大到小,因为变为了负值,对其从小到大就是对其从大到小.

#include<bits/stdc++.h>
#define fp(i,a,b) for(int i=a;i<=b;i++)
typedef long long ll;
typedef double dl;
using namespace std;

const int N=2e5+7;
const int INF=0x3f3f3f3f;

ll n,m;

struct node{
    ll d,q;
}s[N];

ll b[N];

bool cmp(node a,node b)
{
    if(a.q==b.q) return a.d<b.d;
    return a.q<b.q;
}
bool cmp1(int a,int b)
{
    return a>b;
}
multiset<ll> st;
void solve()
{
    while (scanf("%lld %lld",&n,&m)!=EOF)
    {

        st.clear();

        for(int i=1;i<=n;i++)    scanf("%lld",&b[i]),st.insert(-b[i]);
        for(int i=1;i<=m;i++)    scanf("%lld%lld",&s[i].d,&s[i].q),s[i].d=-s[i].d;
        sort(s+1,s+m+1,cmp);
        //sort(b+1,b+n+1,cmp1);
        int sum=0;
        if(n>m)
        {
            printf("No Solution\n");
            continue;
        }
        int flag=0;
        for(int i=1;i<=m;i++)
        {
            if(st.empty()==1)
            {
                flag=1;
                break;
            }
            auto it=st.lower_bound(s[i].d);
            if(it==st.end()) continue;
            sum+=s[i].q;
            st.erase(it);

        }
        if(st.empty())    flag=1;

        if(!flag) printf("No Solution\n");
        else printf("%lld\n",sum);

    }
}

int main()
{
    //ios::sync_with_stdio(0);
    //cin.tie(0),cout.tie(0);
    //int T; scanf("%d",&T);
    //for(int i=1;i<=T;i++)
        solve();
}

//11.22 ccpc省赛
//11.28 天梯赛 
//12.12-13 上海
//12.19-20 南京
//12.26-27 济南