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

前言

日常练习，保持思考。

正文

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);

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

总结

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