分组排序
DescriptionHarryPotter大学毕业后来到了国防部工作。但不幸的是当他工作的第一天，外星人大举入侵地球。HarryPotter被临时调到情报分析部门执行任务。他得到的第一个任务就是对外星人部队的作战能力按从大到小排序。HarryPotter将得到两份情报，一份是外星人每支部队的攻击力，另一份是这些部队的防御力。
当HarryPotter把这些部队按攻击力和防御力分别排好序后，发现有些部队之间是无法比较的，比如两支部队一个攻击力强一些，另一个防御力强一些。HarryPotter将这个信息汇报给了上级，经过一系列商议后上级决定：将所有的部队分为尽可能少的m组，使每组
内的任意两支部队的作战能力均可以比较，然后再对每组的部队进行排序。（部队A与部队B的作战能力可以比较的充要条件是A的攻击力和防御力均大于B或均小于B）
这下HarryPotter可犯难了，他只知道如何对攻击力或防御力进行排序，但是两者接合到一起就不知如何是好了。请你HarryPotter完成他的任务。
Input
第一行读入n。其中n表示外星人部队的数目。
以下有n行，每行有两个正整数Xi，Yi。表示第i支部队的攻击力排在第Xi位，防御力排在第Yi位。（若i！=j，则Xi！=Xj且Yi！=Yj。其中0<Xi,Yi<=n）
规模：0<n<=100000
Output
文件第一行有一个正整数m。表示给这n支部队排序最少要分成m组。
以下n行每行有两个正整数k，s。其中第i行表示第i支部队被分在第k组，并且排在第s位。
Sample Input
输入样例1
2
1 2
2 1
输入样例2
5
3 5
5 4
2 1
4 2
1 3
Sample Output
输出样例1
2
1 1
2 1
输出样例2
2
1 2
2 3
2 1
2 2
1 1
【分析】
看到这道题，首先想到的肯定是先排序，再进行操作。那么我们就按照第一关键字从小到大排序（因为题目说了y各不相同，所以y不用排了）。如样例2，排序后是这样
x y
1 3
2 1
3 5
4 2
5 4 不难发现，这样处理后，x是严格单增的，所以对于原条件x单增且y单增便满足了一半。那么只需要对y进行处理便行了。分析后很容易发现可以贪心。
贪心原则是这样的：顺序讨论排序后的每一个点，然后查找当前点的y。在之前是否有一个在1-y之间的最大值，若有，便将当前点分到与那个最大值的点一个组，然后排名为最大值点的排名加1。否则，便新建一组，置当前点的排名为1。然后添加当前节点。
这个贪心原则是很显然的，在不用考虑x的情况下（已经拍好序了），y自然是与恰小于他的分在一起所用的组数较小。
那么再用一个树来完成查找与添加的操作便行了。（蒟蒻只会用线段树写）。
再回过头来看这道题，其实就是维护每个组的最后一名是谁。然后判断当前节点能否与之前的分在一组。
【代码】
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
int x,y,wjj;
}v[100005]; //输入数组
struct ciocio{
int loc,rank,wjj; //wjj是为了离线操作后按照原顺序输出，loc是分组，rank是排名
}ans[100005]; //答案数组
int Tree[400005]; //Tree是线段树，只需要开一个数组，注意空间要为四倍节点大小。
int N,gr[100005],rank[100005],Max,x; //gr即group记录每个y的分组，rank记录每个y在结构体v中的下标
char t[100];
void _in(int &x) //输入优化
{
char t=getchar();
while(t<'0'||'9'<t) t=getchar();
for(x=t-'0',t=getchar();'0'<=t&&t<='9';x=x*10+t-'0',t=getchar());
}
void _out(int &x,int j=1) //输出优化
{
if(x==0)printf("0");
for(;x;x/=10,j++) t[j]=x%10+'0';
for(j--;j;j--)putchar(t[j]);
}
int _idx(int l,int r) //找线段树某个区间的编号
{
return ((l+r)|(l!=r));
}
bool _cmp_x(node a,node b)
{
return (a.x<b.x);
}
bool _cmp_wjj(ciocio a,ciocio b)
{
return (a.wjj<b.wjj);
}
void _init()
{
_in(N);
for(int i=1;i<=N;i++)
{
_in(v[i].x);_in(v[i].y);
v[i].wjj=i; //输入时处理编号
}
}
void _insert(int l,int r)
{
int id,mid;
id=_idx(l,r);mid=(l+r)>>1;
if(l==r&&r==x)
{
Tree[id]=x;
return;
}
if(l<r)
{
if(l<=x&&x<=mid) _insert(l,mid);
if(mid+1<=x&&x<=r) _insert(mid+1,r);
}
Tree[id]=max(Tree[_idx(l,mid)],Tree[_idx(mid+1,r)]);
}
void _del(int l,int r)
{
int id,mid;
id=_idx(l,r);mid=(l+r)>>1;
if(l==r&&r==x)
{
Tree[id]=0;
return;
}
if(l<r)
{
if(l<=x&&x<=mid) _del(l,mid);
if(mid+1<=x&&x<=r) _del(mid+1,r);
}
Tree[id]=max(Tree[_idx(l,mid)],Tree[_idx(mid+1,r)]);
}
void _findans(int l,int r) //查找时为查找1-x这一段的最大值
{
int id,mid;
id=_idx(l,r);mid=(l+r)>>1;
if(1<=l&&r<=x)
{
Max=max(Max,Tree[id]);
return;
}
if(l<r)
{
if(!(x<l||mid<1)) _findans(l,mid);
if(!(x<mid+1||r<1)) _findans(mid+1,r);
}
Tree[id]=max(Tree[_idx(l,mid)],Tree[_idx(mid+1,r)]);
}
void _solve()
{
int tot=0;
sort(v+1,v+1+N,_cmp_x);
for(int i=1;i<=N;i++)
{
Max=0;
x=v[i].y; //Max和x均为全局变量，方便线段树的各项操作
rank[x]=i;
_findans(1,N);
if(Max==0) //若在1-x这一段没有一个最大值，便新建一个分组
{
tot++;
gr[x]=tot;
ans[i].loc=tot;
ans[i].rank=1;
}
else //若能找到一个在1-x中比他恰小的，便继承那个的分组，然后rank为那个的rank+1；
{
gr[x]=gr[Max];
ans[i].loc=gr[Max];
ans[i].rank=ans[rank[Max]].rank+1;
x=Max;
_del(1,N);
}
x=v[i].y;
_insert(1,N);
}
for(int i=1;i<=N;i++) //对应序号后，重新排序
ans[i].wjj=v[i].wjj;
sort(ans+1,ans+1+N,_cmp_wjj);
_out(tot);putchar('\n');
for(int i=1;i<=N;i++)
{
_out(ans[i].loc);putchar(' ');
_out(ans[i].rank);putchar('\n');
}
}
int main()
{
_init();
_solve();
return 0;
}
补充：综合编程 , 其他综合 ,
