网站建设的开发方式知乎,有没有做美食的视频网站,什么网站可以做微招聘,烟台酒店网站建设题目链接#xff1a; https://vjudge.net/problem/POJ-3067 题目大意#xff1a; 日本岛东海岸与西海岸分别有N和M个城市#xff0c;现在修高速公路连接东西海岸的城市#xff0c;求交点个数。 解题思路#xff1a; 记每条告诉公路为(x,y), 即东岸的第x个城市与西岸的第y个…题目链接 https://vjudge.net/problem/POJ-3067 题目大意 日本岛东海岸与西海岸分别有N和M个城市现在修高速公路连接东西海岸的城市求交点个数。 解题思路 记每条告诉公路为(x,y), 即东岸的第x个城市与西岸的第y个城市修一条路。当两条路有交点时满足x1-x2*y1-y2 0。所以将每条路按x从小到达排序若x相同按y从小到大排序。 然后按排序后的公路用树状数组在线更新求y的逆序数之和 即为交点个数。 比如样例 1 42 33 23 1 排完序后 1 42 33 13 2 1、加入1 4此时比4大的元素为0交点数目为0 2、加入2 3此时比3大的元素数目为1交点数目为1 3、加入3 1此时比1大的数字有两个交点数目为3 4、加入3 2此时比2大的数字有2个交点数目为5 如果先加人3 2再加入3 1的话会导致3 1这条计算交点的时候吧3 2算进去但实际上并没有交点所以排序顺序在x相同的y从小到大排序 1 #includeiostream2 #includecstdio3 #includecstring4 #includestring5 #includemap6 #includeset7 #includecmath8 #includealgorithm9 using namespace std;
10 typedef long long ll;
11 const int maxn 1000000 10;
12 int n, m, T, k, cases;
13 struct node
14 {
15 int x, y;
16 bool operator (const node a)const
17 {
18 return x a.x || x a.x y a.y;
19 }
20 };
21 node a[maxn];
22 int tree[10000];
23 int lowbit(int x)
24 {
25 return x (-x);
26 }
27 ll sum(int x)
28 {
29 ll ans 0;
30 while(x)
31 {
32 ans tree[x];
33 x - lowbit(x);
34 }
35 return ans;
36 }
37 void add(int x, int d)
38 {
39 while(x m)
40 {
41 tree[x] d;
42 x lowbit(x);
43 }
44 }
45 int main()
46 {
47 cin T;
48 while(T--)
49 {
50 cin n m k;
51 memset(tree, 0, sizeof(tree));
52 for(int i 1; i k; i)
53 {
54 scanf(%d%d, a[i].x, a[i].y);
55 }
56 sort(a 1, a 1 k);
57 ll ans 0;
58 for(ll i 1; i k; i)
59 {
60 add(a[i].y, 1);
61 ans (i - sum(a[i].y));
62 }
63 printf(Test case %d: %lld\n, cases, ans);
64 }
65 return 0;
66 } 转载于:https://www.cnblogs.com/fzl194/p/8946869.html
