已知数轴上0<N<10000条线段。每条线段按照端点Ai和Bi（Ai<>Bi,i=1..N）定义。端点坐标在（-999，999）内，坐标为整数。有些线段可能相交。编程实现删除最少数目的线段，使得余下的任意两条线段不相交。
第一行为一整数N。接下来有N行，每行包含两个整数 (Ai 和 Bi), 用空格隔开。
输出格式：
整数p，即删除后余下的线段数。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
贪心~
显然DP能做，但是比较神奇的是贪心~
上来就写了个超长（相对于这题来说）代码，然后发现那种思路是错的连样例都过不了……TAT
然后，正确的贪心方法是以线段右端点为关键字排序，记录现在的最右端点位置，从1~n扫一遍，每次左端点不小于now时，ans++，更新now~
正确性：假设现在有两线段a,b，其中b.r>a.r，
（1）若b.l<a.l，a被b完全包含，显然a优于b，b可以舍弃；
（2）若b.l>=a.l，且存在c使得c.r<b.l && c.r>a.l，那么这个c会先于a更新答案，从而使得a无法计入结果，答案更优。
所以就是几行的贪心啊！
#include<cstdio> #include<algorithm> using namespace std; int n,ans,now; struct node{ int l,r; }a[10001]; int read() { int totnum=0,f=1;char ch=getchar(); while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();} while(ch>='0' && ch<='9') {totnum=(totnum<<1)+(totnum<<3)+ch-'0';ch=getchar();} return totnum*f; } bool operator < (node u,node v) { return u.r<v.r; } int main() { n=read();now=-999; for(int i=1;i<=n;i++) { a[i].l=read(),a[i].r=read(); if(a[i].l>a[i].r) swap(a[i].l,a[i].r); } sort(a+1,a+n+1); for(int i=1;i<=n;i++) if(now<=a[i].l) ans++,now=a[i].r; printf("%d\n",ans); return 0; }
错误的代码，前车之鉴啊：
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define b(u) b[u+1000] #define c(u) c[u+1000] int n,ans,c[2000]; bool b[2000]; struct node{ int l,r; }a[10001]; int read() { int totnum=0,f=1;char ch=getchar(); while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();} while(ch>='0' && ch<='9') {totnum=(totnum<<1)+(totnum<<3)+ch-'0';ch=getchar();} return totnum*f; } bool operator < (node u,node v) { return u.r-u.l==v.r-v.l ? u.l<v.l:u.r-u.l>v.r-v.l; } void chan(int u,int v) { int l=min(a[u].l,a[v].l),r=max(a[u].r,a[v].r); for(int i=l;i<=r;i++) { if(i>=a[u].l && i<=a[u].r) b(i)=0; if(i>=a[v].l && i<=a[v].r) b(i)=1; } } int main() { n=read(); for(int i=1;i<=n;i++) { a[i].l=read(),a[i].r=read(); if(a[i].l>a[i].r) swap(a[i].l,a[i].r); } sort(a+1,a+n+1); for(int i=1;i<=n;i++) if(!b(a[i].l) && !b(a[i].r)) { ans++; for(int j=a[i].l;j<=a[i].r;j++) b(j)=1; } else { int la1=c(a[i].l),la2=c(a[i].r); if(la1) { if(!la2) chan(la1,i); } else chan(la2,i); } printf("%d\n",ans); return 0; }