题解 | #牛可乐与NCPC#
牛可乐与NCPC
https://ac.nowcoder.com/acm/problem/235569
沃趣,这题看了好久，看了AC代码思考许久才弄明白题目意思(题目特别绕，看不懂题！悲╰（‵□′）╯）
一、这题意思是考虑队伍 i ，如果在观察列表中有aj和bj都小于 i 的a，b，或者有一个数等于另一个小于的时候队伍i就不放入观察列表
二、放入观察列表有两种情况
1、列表中没有两个都比我大或者一个等于我另一个比我大的情况，就直接入列
2、不然就删去比我大的然后入队，删除操作贼难
再删除之前肯定得排序，这里用的是multiset，利用lower_bound和upper_bound快速找到两个数都大于等于我的最小位置和最大位置
首先排序之后，观察列表内部顺序是前一个a小后一个a大，因为不可能同时出现后面一个的a，b都大于前面的a，b，那么一定是前一个a小，后一个数b小(重点)
得到的序列就是a一直增大，b一直减小 ，到这一步就很明朗了
直接lower_bound()返回第一个大于等于我的数如果这个数(返回的是后一个位置，所以要减1)的b大于我那就入列并去判断是不是要删除
然后再考虑删除的时候从第一个都大于我的开始考虑，后面的数肯定是a都大于我，但b肯定是一直减小的，一直枚举到b不大于我的时候就可以结束了
一些其他考虑的问题在代码里面
//想看纯代码往下翻
#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
struct node
{
int a,b;
bool operator < (const node& other) const{
if(a!=other.a) return a<other.a;
else return b<other.b;
}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;cin>>t;
for(int j = 1; j <= t; j ++)
{
cout<<"Case #"<<j<<":"<<endl;
int n;cin>>n;
multiset<node>s; // 自动排序
node temp;
for(int i = 1; i <= n; i ++)
{
cin>>temp.a>>temp.b;
auto t = s.lower_bound(temp);
//找到第一个大于a,b的最小位置
//那么前面的a一定是都比ai大的，如果有bj比bi还小就满足两个都小于的情况就不能入队
//那就要找到b的最小值也就是t的前一个位置如果这个大于bi那就可以入队
//等于s.begin()是一个特殊情况（这里数据也不够强）
//如果t->a大于temp.a只需要(--t)->b>=temp.b就可以,否则(--t)->b>temp.b就行
//测试样例很多，但数据没有卡死在这些点上不然就更难了
if(t == s.begin()||((--t)->b)>temp.b)
{
auto item = s.upper_bound(temp);
//返回第一个大于等于tmep的最小位置
//那么从这个位置开始后面的a一定大于等于temp.a，但b是减小的
//(可能数据不够强,没有出现等于a，但是大于b的情况)
while(item!=s.end()&&item->b>temp.b)s.erase(it++);
/*while(item!=s.end()&&item->b>=temp.b)
{
if(item->b>temp.b)s.erase(it++);
else if(item->a>temp.a)s.erase(it++);
//这个原因是item->a 变大到大于temp.a然后如果b减小到正好是temp.b这个时候删不掉
//所以要这里要特判一下item.b==temp.b的时候item.a是不是大于temp.a
}*/
s.insert(temp);
}
cout<<s.size()<<endl;
}
if(j!=t)cout<<endl;
}
}
//纯享版
#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
struct node
{
int a,b;
bool operator < (const node& other) const{
if(a!=other.a) return a<other.a;
else return b<other.b;
}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;cin>>t;
for(int j = 1; j <= t; j ++)
{
cout<<"Case #"<<j<<":"<<endl;
int n;cin>>n;
multiset<node>s;
node temp;
for(int i = 1; i <= n; i ++)
{
cin>>temp.a>>temp.b;
auto t = s.lower_bound(temp);
if(t == s.begin()||((--t)->b)>temp.b)
{
s.insert(temp);
auto it = s.upper_bound(temp);
while(it!=s.end()&&it->b>temp.b)s.erase(it++);
}
cout<<s.size()<<endl;
}
if(j!=t)cout<<endl;
}
}
搜狐畅游公司福利 901人发布
