坦克游戏3519
【题目描述】
Lemon最近迷上了一款坦克对战游戏。在这款游戏中，Lemon需要驾驶一辆坦克与敌军对战。坦克有很多不同的武器，每种武器有各自的特点，而Lemon所要做的就是合适地发射这些武器，对敌军造成最大的伤害。具体来说，每个武器都有两个参数：攻击力D和攻击半径R。为了简化题意，我们保证所有武器的攻击力D均不相同，所有武器的攻击半径R也均不相同。Lemon决定对这些武器的性能进行评价。当然，评价不能只看攻击力D，也不能只看攻击半径R。Lemon觉得一件武器A优于另一件武器B，当且仅当A的攻击力大于B的攻击力且A的攻击半径大于B的攻击半径。
接下来，Lemon想要对武器进行分组，Lemon按照以下方式分组：
首先，我们定义f(A,S)为真当且仅当在武器集合S中的任何武器都不比武器A性能更优秀。
1.令i=0
2.令i=i+1 令S=还没被分组的武器集合
3.对于每一件S中的武器A，如果f(A,S)为真，则将武器A标记为第i组（注意S在这个过程中始终保持不变）
4.如果所有武器均被分组则结束，否则转2
给定N个武器的D和R，你的任务是按照Lemon的规则对这些武器进行分组。
【输入格式】
输入文件第一行包含一个正整数N，表示武器的个数。
接下来N行，每行两个正整数D，R，描述一件武器的攻击力和攻击半径。保证所有的D两两不同，所有的R两两不同。
【输出格式】
输出文件包含N行，每行一个正整数，第i行的数表示第i件武器被分在了哪一组。
【输入样例】
5
1 4
2 2
3 3
4 1
5 5
【输出样例】
2
3
2
2
1
【样例解释】
首先我们发现武器5比武器1性能更优，所以武器1不在第1组。同理武器2、3、4也不在第1组。但没有武器比武器5性能更优，因此武器5在第1组。
接下来还剩武器1、2、3、4没被分组。我们发现这些武器中没有武器比武器1更优，于是武器1在第2组，同理武器3、4也在第2组。
接下来只剩武器2了，武器2在第3组。
此时所有武器均被分组，过程结束。
【数据规模约定】
时间限制为1s
对于20%的数据，N<=100.
对于40%的数据，N<=3000.
对于100%的数据，N<=100000，1<=R,D<=10^9.
官方题解;
此题20%数据的做法显然，直接照着题目要求模拟即可，O(N^3)
此题40%数据做法也比较简单，有两个做法：
1.对20%的做法进行改进，预先对所有的武器按D值排序，这样查找有没有更优的武器时直接查找D值比它大的就行了，时间复杂度可以证明被均摊到了O(N^2)。
2.依然预先对所有武器按D值从小到大排序，然后每次扫一遍，用一个单调栈维护即可，只要遇到R值比栈顶大就弹栈，否则入栈。扫一次就能得出一组，也是O(N^2)的。
此题满分做法是对上一个做法的改进。
仔细观察题目的流程，我们可以发现一个更优的做法。
首先我们发现同一组内的武器，按D值从大到小排序后，R值必然也是从小到大的。
而且我们发现，如果一件武器A的D值比另一件武器B的D值大，那么武器B不会影响到武器A的分组。
于是考虑把武器按D值从大到小排序，然后逐个加入武器，并为新加入的武器找到合适的组。因为在新加入一件武器之前，我们已经加入了所有D值更大的武器，而剩下的武器都不会影响当前武器的分组，所以现在得出的组号就是最终的组号。
假设D值最大的前x个武器已经全部加入组，而且现在已经有k组了， 定义第i组里最大的R值为maxR(i)，那么我们发现maxR(i)必然随i递减。
我们考虑加入第x+1个武器，我们发现，按照题目要求，这件武器必然会加入到第i组，i是最小的让maxR(i)<D成立的i值。
于是我们直接用数组存储所有组的maxR，新加入武器时二分查找到加入位置，然后更新对应的那个maxR即可。
时间复杂度O(NlgN)
本人感想：
首先我一开始还是想到了先对某一维进行排序，然后再次对另一维进行操作，但是我发现很难维护R值，有一点逆序对的感觉
看了题解之后我认为这种题目还是需要先进行手动的模拟，然后才能说找到了规律（但是先排序后思考必须是基本操作）
发现如果不是偏序就一定会在一个组里面，然后我们就会发现如果是偏序就一定不在一个区间，这就是我们探究不同组的条件
然后我们再来看顺序问题，题目中很显然是先把综合能力高的先给排进去，说明D，R都是最大的
我们维护了D，所以之后我们维护R就可以了，后面不会影响前面的决策理解如下：
D肯定比前面小，所以如果R比前面大就直接放到前面去
R比前面小自然就要新开一组
一般这种题我们维护了一维之后我们要对另一维要么进行区间操作，要么进行最值操作，总之我们维护R的时候应该抛弃D，二分
code:
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #define N 1000006 5 using namespace std; 6 struct node{ 7 int d,r,id,gr; 8 }e[N]; 9 bool cmp(const node&a,const node &b){ 10 return a.d>b.d; 11 } 12 bool bmp(const node&a,const node&b){ 13 return a.id<b.id; 14 } 15 int R[100006],now; 16 int main(){ 17 int n; 18 cin>>n; 19 for(int i=1;i<=n;i++){ 20 cin>>e[i].d>>e[i].r; 21 e[i].id=i; 22 } 23 sort(e+1,e+n+1,cmp); 24 // for(int i=1;i<=n;i++){ 25 // cout<<"l->"<<e[i].d<<" r->"<<e[i].r<<' '; 26 // } 27 for(int i=1;i<=n;i++){ 28 if(!now){//如果一开始是空的那么就要加进去 29 R[++now]=e[i].r; 30 e[i].gr=now; 31 continue; 32 } 33 if(e[i].r<=R[now]){//如果比最小的都要小 34 R[++now]=e[i].r;//新开一组 35 e[i].gr=now;//归属确定 36 continue; 37 } 38 int l=1,r=now,ans; 39 while(l<=r){ 40 int mid=l+r>>1; 41 if(R[mid]>=e[i].r)l=mid+1; 42 else r=mid-1,ans=mid; 43 } 44 R[ans]=e[i].r; 45 e[i].gr=ans; 46 // R[pos]=e[i].r; 47 // e[i].gr=pos; 48 } 49 sort(e+1,e+n+1,bmp); 50 for(int i=1;i<=n;i++)cout<<e[i].gr<<' '; 51 return 0; 52 }
over