求道路的交叉点数。
将道路按左边城市从大到小排序。如果相同则按右边从大到小排序。
这样就跟stars和cows一样了。
#include <iostream> #include <algorithm> using namespace std; const int maxn = 1010; int c[maxn],result[maxn]; typedef struct { int e, s; } node; node nd[maxn * maxn]; bool cmp(node a , node b) { if(a.s == b.s) return a.e > b.e; return a.s > b.s; } int Lowbit(int x) { return x & (-x); } void Update(int x) { int i; for(i = x; i < maxn; i += Lowbit(i)) { c[i]++; } } int Getsum(int x) { long long sum = 0; int i; for( i = x; i > 0; i -= Lowbit(i) ) { sum += c[i]; } return sum; } int main() { int t; scanf("%d", &t); for(int cas = 1; cas <= t; cas++) { int l, r; int n; scanf("%d%d%d", &l, &r, &n); memset(c, 0, sizeof(c)); memset(result, 0, sizeof(result)); int x, y; for(int i = 1; i <= n; i++) { scanf("%d %d", &x, &y); nd[i].s = x + 1; nd[i].e = y + 1; } sort(nd+1, nd+n+1, cmp); long long sum = 0; for(int i = 1; i <= n; i ++) { sum += Getsum(nd[i].e - 1); //注意这里要减1 Update(nd[i].e); } printf("Test case %d: %lld\n", cas, sum); } return 0; }