把给出的哨所按A值升序排序后，对于某个哨所，如果他的B值小于他之前的所有哨所的B值的最大值，那么他就应该被裁减掉，反之留下。
　　上面的排序方法不对，不仅要按A值升序，对A值相同的，还要按B值降序。
　　Submit 1: WA on 2。又一个<写成<=了。（错误的Debug）
　　Submit 2: WA on 2。还是没有看清题目要求：题目要求A_j>A_i,B_j<b_i的哨所j被裁减，我上面的做法变成了A_j\ge A_i,B_j<b_i的哨所被裁减。应该把A值相同的哨所作为一“段”。对于某个哨所，应该拿他的B值与他所在的“段”之前的所有哨所的最大B值比较，而不是与他自身之前的所有哨所的最大B值比较。（错误的Debug）
　　Submit 3: WA on 1。不对，今天是怎么回事，老看错题。题目已经写明了：所有的A都不一样，所有的B也都不一样。所以按最初算法，排序之后，所有的哨所已经是按A值升序了，不会有A值相同的哨所。错误都出在别的地方。倒……排序排反了……

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

//AC
#include <cstdio>
#include <cstdlib>
using namespace std;
 
struct outpost
{
    long a,b;
};
 
int compare(const void *tp1,const void *tp2)
{
    const outpost *p1=(outpost*) tp1;
    const outpost *p2=(outpost*) tp2;
    return (p1->a<p2->a)?-1:1;
}
 
int main()
{
    long n,maxb(-1),r(0);
    outpost outposts[16000];
    scanf("%ld",&n);
    for (long i=0;i<n;++i)
        scanf("%ld %ld",&outposts[i].a,&outposts[i].b);
    qsort(outposts,n,sizeof(outpost),compare);
    for (long i=0;i<n;++i)
    {
        if (outposts[i].b<maxb) ++r;
        else maxb=outposts[i].b;
    }
    printf("%ld\n",r);
    return 0;
}