HDU 4268 Alice and Bob setの使い方
2127 ワード
タイトルの住所: http://acm.hdu.edu.cn/showproblem.php?pid=4268
欲张り思想は、setでバランスツリーを実现しますが、setには唯一性がありますので、multisetを使います。
ACコード:
欲张り思想は、setでバランスツリーを実现しますが、setには唯一性がありますので、multisetを使います。
ACコード:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
using namespace std;
typedef long long LL;
const int N=100005;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
struct xh
{
LL x,y;
int t;
}a[N<<1];
LL get_ll()
{
LL sum=0;
char c;
while((c=getchar())>'9'||c<'0')
;
sum=c-'0';
while((c=getchar())<='9'&&c>='0')
sum=sum*10+c-'0';
return sum;
}
bool cmp(xh a,xh b)
{
if(a.x!=b.x)
return a.x<b.x;
if(a.y!=b.y)
return a.y<b.y;
return a.t<b.t;
}
int main()
{
int i,j,T,n;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
{
a[i].x=get_ll();
a[i].y=get_ll();
a[i].t=1;
}
for(i=n;i<2*n;i++)
{
a[i].x=get_ll();
a[i].y=get_ll();
a[i].t=0;
}
sort(a,a+2*n,cmp);
multiset<int> se;
se.clear();
int cnt=0;
i=j=0;
for(i=0;i<2*n;i++)
{
if(a[i].t==0)
se.insert(a[i].y);
else
{
if(!se.empty())
{
if(a[i].y<*se.begin()) continue;
multiset<int>::iterator it;
it=se.upper_bound(a[i].y);
it--;
cnt++;
se.erase(it);
}
}
}
printf("%d
",cnt);
}
return 0;
}