不妨将某条桥的左断点设成x ,右端点设成y 。
先将这些桥按照x 排序, x相同时按照y 排序。
这样的话和数星星那题就很像了。
对于某一条桥,我们只需要考虑它之前的y 坐标比它大的的桥的个数, 这样用逆序数就行 ,即可以用i - sum(qiao[i].y) 。
即可。
AC Memory:3300 KB Time : 391 ms
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int n,m,k; int c[1005]; struct way { int x,y; } w[1005*1005]; bool cmp(way a,way b) { if(a.x!=b.x) { return a.x <b.x; } else { return a.y <b.y; } } int lowbit(int x) { return x&(-x); } void update(int i,int val) { while(i<=m) { c[i]+=val; i+=lowbit(i); } } int sum(int i) { int s = 0; while(i>0) { s+=c[i]; i-=lowbit(i); } return s; } int main() { int T; int count = 0; cin>>T; while(T--) { count++; cin>>n>>m>>k; memset(c,0,sizeof(c)); for(int i = 0;i<k;i++) { scanf("%d%d",&w[i].x,&w[i].y); } sort(w,w+k,cmp); long long res = 0; for(int i = 0;i<k;i++) { res += i - sum(w[i].y); update(w[i].y,1); } printf("Test case %d: %I64d\n",count,res); } return 0; }