程序员进阶之算法练习（二十七）

前言

日常练习，保持思考。

正文

1.Parallelogram is Back

题目链接
题目大意：
给出平行四边形的三个点(x[i], y[i])，求出可能的第四个点的坐标。
先输出可能数m，接下来m行，每行两个数，表示点的x和y坐标。

ABCD就是平行四边形

输入数据：
x[i] and y[i] ( - 1000 ≤ x[i], y[i] ≤ 1000)

Examples
input
0 0
1 0
0 1
output
3
1 -1
-1 1
1 1
样例解释：(0, 0),(1,0),(0,1)与(1,-1)可以形成平行四边形，(-1, 1),(1,1)同样可以。

题目解析：
给出平行四边形的三个点，那么三个点必然可以连成一个三角形。
过三角形的每条边，都可以做一个平行四边形，所以可能的点固定为3个。

cout << 3 << endl;
cout << a[0] + (c[0] - b[0]) << " " << a[1] + (c[1] - b[1]) << endl;
cout << b[0] + (a[0] - c[0]) << " " << b[1] + (a[1] - c[1]) << endl;
cout << c[0] + (b[0] - a[0]) << " " << c[1] + (b[1] - a[1]) << endl;

2. Pizza Separation

题目链接
题目大意：
题目大意：小明有一个圆披萨，分成n块（扇形）；（1<=n<=360)
每块的角度是ai，并且总的角度和是360。
把这些披萨分成连续的两部分，求两部分披萨的最小角度差。

Examples
input
4
170 30 150 10
output
0
样例解析：

如图，小明可以选择把1，4分在一起，2，3分在一起，最小的角度差是0。

题目解析：
分成两部分，并且差最小，相当于尽可能逼近180°。
又因为题目要求是连续，所以直接枚举区间的起点和终点，大概是360^2的复杂度。

思考🤔：
如果改成不连续的俩部分呢？

180容量的背包。

3.Voting

题目链接
题目大意：
n个人分配两派，分别用D、R表示两派；
现在n个人进行选举，每个人轮流投票，每次投票是选择一个人退出选举；直到剩下最后一个人，这个人代表的阵营胜利。
每次都是从左到右进行投票，假设他们的投票都是理性的，问最后哪方阵营能获胜？

输入数据：
n (1 ≤ n ≤ 200 000)

Examples
input
5
DDRRR
output
D
样例解释：
第一轮投票：
1号 否决 5号；
2号 否决 3号；
3号 退出；
4号 否决 2号；
5号 退出；
第二轮投票：
1号 否决 4号；
2号 退出；
4号 退出；
只剩下1号，所以1号的阵营D胜利。

题目解析：
每个人会淘汰一个人出局，那这个人必然是对方阵营，如果不得已要淘汰己方的阵营，那就代表着胜利；
那么，每个人必然会选择距离下一次投票最近的敌方阵营的人；
那么模拟一遍，直到获取结果。

时间复杂度：每次至少淘汰n/2个人，log(N)次数，每次O(N)的时间，总得复杂度是O(NlogN);
空间复杂度：循环利用原来的数据，空间复杂度为O(N);

4.XK Segments

题目链接
题目大意：
给出一个数组a，一个整数x。
pair(i, j)的定义是： 满足a[i]<=a[j]，且存在k个整数y，a[i]<=y<=a[j] 和 y%x等于0；
pair(i, j）等于pair(j, i) 当且仅当 i==j;
求满足要求的所有pair数量。

输入数据：
n, x, k (1 ≤ n ≤ 1e5, 1 ≤ x ≤ 1e9, 0 ≤ k ≤ 1e9)
a[i] (1 ≤ a[i] ≤ 1e9)

Examples
input
4 2 1
1 3 5 7
output
3
样例解释：
pair(1,2), pair(2,3), pair(3,4)满足要求；
当k==1，x==2时，对于pair(1,2)，满足a[1]<=a[2]，且存在1个整数y，满足a[1]<=y<=a[2] 和 y%2==0；（y=2）

题目解析：
根据题意，pair(i, j)要求在区间[a[i], a[j]]中存在k个x的倍数；
假设pair(i, j)满足要求，且t是区间中x的倍数最小的一个，那么剩余满足%x==0的数字必然是t+x,t+2*x,t+3*x....直到t+(k-1)*x;

为了方便，先将数组排个序；（从小到大）
我们设p = ((a[i]+x-1)/x)*x; （大于等于a[i]，能被x整除的最小整数）
那么取值区间就是[p+(k-1)*x, p+k*x)；
特殊的，当k=0的时候，p+(k-1)*x=p+x，是不合理的，此时的区间应该是[a[i], p+k*x);（题目有要求,a[i]<=a[j])
故而答案是[max(a[i], p+(k-1)*x, p+k*x)；

思考🤔：
trick -- long long。

5.Leaving Auction

题目链接
题目大意：
n个人在竞标物品，轮流出价，最终价高者得；
现在已知整个竞标过程总共有n次出价，用(a[i], b[i])来表示第i次竞标中，第a[i]个人，出价为b[i]；

q个询问，每个询问首先是k，表示假如k个人没来，接下来是k个整数，表示k个没来人的序号；
对于每个询问，输出最终的竞标结果；

输入数据：
a[i] and b[i] (1 ≤ a[i] ≤ n, 1 ≤ b[i] ≤ 1e9, b[i] < b[i] + 1)
n (1 ≤ n ≤ 200 000)
q (1 ≤ q ≤ 200 000)
询问总数(1 ≤ sum of all k ≤ 200 000)

Examples
input
6
1 10
2 100
3 1000
1 10000
2 100000
3 1000000
3
1 3
2 2 3
2 1 2
output
2 100000
1 10
3 1000
样例解释：
当3号没来参加时，竞标过程是
1 10
2 100
1 10 000
2 100 000
2号出价100 000竞标成功；
当2、3号没来参加时，竞标过程是
1 10
1 10 000
1号竞标成功，但是因为1号不会出价超过自己，所以最终是出价10竞标成功；
类似当1，2号没来参加时，最终1000竞标成功。

题目解析：
题目比较拗口，重点在于某部分人不来的情况，如何快速求出竞标的结果。
q的数量较大，能够接受的时间复杂度在O(logN);
先看看题目给出的条件，bi < bi + 1 并且 ai ≠ ai + 1；
那么，越后面出价的数字会越高，直接通过最后面可以知道最高价；
看看询问会造成的影响：
1、某些人不来，其竞标的价格无效，本来可能是他的最高价，会顺延下一个人；
2、假设某个人出了最高价，但是因为某些人没来，导致他的次高价也是最高的，这时候会选择次高价；

那么有一种办法是：
每个人的竞标结果，按大小顺序放到自己的一个桶里；
每个桶按照最高价作为权值进行排序；

每次找到有效的、权值最高的桶，这个人会中标；
接着找到次高的桶，在最高的桶里面选择一个比次高桶的权值更高的竞标作为低价；

复杂度分析：
把每个人的竞标结果分类，O(N); N是竞标的数量
每个桶排序，O(MlogM); M是桶的数量

对于每个询问，找到权值最高的桶，这里用遍历操作；
找到权值最高的桶之后，继续找权值次高的桶，这里仍然用的遍历操作；
这两个操作的复杂度取决于每个询问中，不来人的数量，因为询问总数为N，所以复杂度是O(N);
在权值最高的桶里面找一个竞标，比次高桶的权值更高的，这里用二分查找，复杂度是O(logN)，次数可能会有O(N)次；
总的复杂度是 O(NlogN);

思考🤔：
很有意思的题目，看着挺复杂，实际写起来代码很短。

总结

立个小目标，今年要更新算法练习（五十）。
会做算法题不是万能的，不会做算法题是万万不能的。