C - AtCoder Magics 贪心
作者:
多米尼克領主的致意
,
2024-05-19 15:10:15
,
所有人可见
,
阅读 3
贪心策略是保留下A更大而C更小的值
那么先按A升序排序
将这个序列依次放入栈中,后进入的C如果值小于栈顶的值,那么出栈,直到栈顶的值小于
要进栈的值
这个过程保证了删除的top卡牌A小于要进栈的x卡牌,C大于x卡牌。
最后按id顺序升序set
code:
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
typedef pair<int, int>pii;
int n;
int a[N];
struct node{
int a, c;
int id;
bool operator < (const node& rhs)const{
return a < rhs.a;
}
}card[N];
stack<pii>s;
set<int>ans;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1;i <= n;i++){
cin >> card[i].a >> card[i].c;
card[i].id = i;
}
sort(card + 1, card + 1 + n);
s.push({card[1].c, card[1].id});
for(int i = 2;i <= n;i++){
auto t = s.top();
while(card[i].c < t.first){
s.pop();
if(s.empty())break;
t = s.top();
}
s.push({card[i].c, card[i].id});
}
while(s.size()){
ans.insert(s.top().second);
s.pop();
}
cout << ans.size() << endl;
while(ans.size()){
cout << *ans.begin() << " ";
ans.erase(*ans.begin());
}
return 0;
}