ABC354

C

multiset和sort,同时维护两个数组,好题,力量最强的并且花费最小的

#include<bits/stdc++.h>

using namespace std;

const int N = 3e5+20;

struct Node
{
    int a,c,id;//a是力量,c是花费,id是编号
    bool operator <(const Node &t)const{
        return a<t.a;
    }
}a[N];

int n;
multiset<int>st;//维护所有力量大于当前卡牌的花费
vector<int>ans;//存储最强卡片的编号

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].a>>a[i].c;
        a[i].id=i;//存储编号
        st.insert(a[i].c);
    }
    
    sort(a+1,a+n+1);
    int j=1;
    for(int i=1;i<=n;i++)
    {
       while(j<=n&&a[i].a==a[j].a)
       {
           st.erase(a[j++].c);//每次遍历到一张卡牌时,用一个指针将所有力量与当前卡牌相同的卡牌的花费从set中删除掉
           //这样set中所有元素对应的力量都是比当前卡牌大的
       }
       if(st.empty()||*st.begin()>=a[i].c)
       {
           ans.push_back(a[i].id);//把留下来的卡牌的编号存到ans中
       }
    }
    sort(ans.begin(),ans.end());//按照升序输出
    cout<<ans.size()<<endl;
    for(auto man:ans)cout<<man<<" ";
    
    return 0;
}
//38行那么只要存在其中一张的花费比当前卡牌小，当前卡牌就会被删除，
//即，只有当前卡牌的花费比后面所有牌的花费均小（小于等于），当前卡牌就不会被删除，由于multiset也会排序，
//那么只需要与multiset存储的第一个元素比较即可，如果当前卡牌的花费小于等于存储的最小的花费，那么当前卡牌就会被保留。
//也就是说后面的卡牌的力量比你大,但是你的花费比后面的卡牌小,那么你就会留下来