程序员进阶之算法练习（九十八）
题目1
题目链接 题目大意： 在一个国际象棋的棋盘上，有一个棋子，它的移动规则类似马，能够朝着横or竖方向移动距离a，然后朝竖or横（和之前不同）移动距离b； 比如说马的移动规则就是a=1，b=2；
现在棋盘上还有另外两个棋子K和Q，问棋盘上有多少个特殊位置，在该位置上面可以移动棋子K所在位置，也可以移动到棋子Q所在位置。
如下，该图上面的马，可以移动到另外两个棋子的位置。
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1000) 每个样例3行 第1行整数 𝑎 and 𝑏 (1≤𝑎,𝑏≤1e8) 第2行整数 𝑥𝐾 and 𝑦𝐾 (0≤𝑥𝐾,𝑦𝐾≤1e8 ) 第3行整数 𝑥𝑄 and 𝑦𝑄 (0≤𝑥𝑄,𝑦𝑄≤1e8 )
输出： 每个样例一行，输出满足要求的位置数量。
Examples input 4 2 1 0 0 3 3 1 1 3 1 1 3 4 4 0 0 8 0 4 2 1 4 3 4
output 2 1 2 0
题目解析： 能够攻击到k的位置，应该有左右上下8个角落； 同理，能够攻击到q的位置，也同样有8个角落； 接下来枚举前面的位置，看是否有位置与后面的角落重合，即可。
tips： 1、为了方便枚举，可以把4个方向用dir[4][2]的数组来枚举； 2、a和b不相同的时候，要考虑a和b互换的情况；
typedef long long lld;
class Solution {
static const int N = 201010;
int dir[4][2] = {1,1, -1,1, 1,-1, -1,-1};
public:
void solve() {
int t;
cin >> t;
while (t--) {
int val[2], x1, y1, x2, y2;
cin >> val[0] >> val[1];
cin >> x1 >> y1;
cin >> x2 >> y2;
int ans = 0;
for (int i = 0; i < 8; ++i) {
int a = val[i % 2];
int b = val[(i + 1) % 2];
if (a == b && i % 2) continue;;
int idx1 = dir[i/2][0] * a + x1;
int idy1 = dir[i/2][1] * b + y1;
for (int j = 0; j < 8; ++j) {
int a2 = val[j % 2];
int b2 = val[(j + 1) % 2];
if (a2 == b2 && j % 2) continue;;
if ((idx1 + dir[j/2][0] * a2 == x2) && (idy1 + dir[j/2][1] * b2 == y2)) {
++ans;
break;
}
}
}
cout << ans << endl;
}
}
}
ac;题目2
题目链接 题目大意： 有n个元素的整数数组a，现在进行以下操作： 1、选择某个元素a[i]，移除当前元素a[i]，获得初始分数score=a[i]； 2、寻找某个元素a[j]，并且满足score>=a[j]，可以移除元素a[j]，同时使得分数score增加a[j]； 3、不断重复操作2，直到无法执行；
现在想知道，每个元素被作为初始元素时，最多能够移除的元素数量；
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤5000) 每个样例2行 第1行整数 𝑛 (1≤𝑛≤1e5 ) 第2行n个整数 𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤1e9)
输出： 每个样例一行，每行n个整数，第i个数字，表示当第i个元素作为初始元素时，能够移除的最多元素数量。（也就是操作2的最多执行次数）
Examples input 4 5 20 5 1 4 2 3 1434 7 1442 1 1 5 999999999 999999999 999999999 1000000000 1000000000
output 4 3 0 3 1 1 0 2 0 4 4 4 4 4
题目解析： 将整数数组进行从大到小排序，接着下来再考虑如何决策； 由于题目的规则很像“大鱼吃小鱼”，可以从数字较小者开始，也就是从右到左： 1、最小的元素，除非和倒数第二个相同，否则无法吃下任何数字； 2、从倒数第二个数字开始，每次可以直接累加右边所有的数字，然后如果数字和大于等于左边的数字，就可以一直累加，然后左移一位，直到无法移动； 此时，该段区间内的所有数字，最终的数字和都是一样的； 3、重复上面的过程，直到将整个数组分为若干段； 比如说[20, 5,4,2,1]就可以分为[20],[5,4], [2], [1]，划分规则就是每次从右到左累加和，小于左边一个数字。
类似的思考过程，假设我们排序之后是从左到右去思考，还是以[20, 5,4,2,1]为例子。 当处理数字20时，按照规则，右边所有数字都能吃掉，ans[0]=4； 当处理数字5时，如果5左边所有数字累加和大于20，那么就可以吃掉20，此时结果ans[1]=ans[0]; 但是5左边累加数字和，结果是12，那么此时结果就是3； 因为数组比较长，右边和可以先计算整个数组和sum，然后不断累积减去当前数字。
typedef long long lld;
class Solution {
static const int N = 101010;
pair<int, int> a[N];
int ans[N];
static bool cmp(pair<int, int> x, pair<int, int> y) {
return x.first > y.first;
}
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
lld sum = 0;
for (int i = 0; i < n; ++i) {
cin >> a[i].first;
a[i].second = i;
sum += a[i].first;
}
sort(a, a + n, cmp);
for (int i = 0; i < n; ++i) {
sum -= a[i].first;
if (i == 0) {
ans[a[i].second] = n - i - 1;
}
else {
if (sum + a[i].first >= a[i - 1].first) {
ans[a[i].second] = ans[a[i - 1].second];
}
else {
ans[a[i].second] = n - i - 1;
}
}
}
for (int i = 0; i < n; ++i) cout << ans[i] << " ";
cout << endl;
}
}
}
ac;题目3
题目链接 题目大意： 有n个整数的数组a，现在可以进行下面的操作： 选择数组中任意两个元素，将两个元素差值的绝对值，插入到数组中的最后面；
现在可以进行上面的操作k次，要求让数组中的最小值在操作之后，尽可能的小；
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1000) 每个样例2行 第1行整数𝑛 and 𝑘 (2≤𝑛≤2⋅1e3 , 1≤𝑘≤1e9 ) 第2行n个整数 𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤1e18)
输出： 每个样例一行，输出操作后的最小值。
Examples input 4 5 2 3 9 7 15 1 4 3 7 4 15 12 6 2 42 47 50 54 62 79 2 1 500000000000000000 1000000000000000000
output 1 0 3 500000000000000000
题目解析： 数组a都是大于1的值，那么最终的结果必然是大于等于0； 当n=2的时候，如果a1=a2，那么结果就是0； 如果a1!=a2，那么|a1-a2|必然会产生一个新的数字，以[4, 2]为例： 4 2 4 2 2 4 2 2 0
但是，当a1和a2差距较大时，我们有： 10 2 10 2 8 10 2 8 2 10 2 8 2 0
也就是当操作次数没有限制时，我们必然能够产生0，比如说： c=b-a； d=b-c=(b-(b-a))=a; 这样数组[a, b, c, d]，只需要选择a-d=a-a=0； 只要k>=3，必然可以得到0。
当k==1时，直接枚举两两想减的情况，得到结果； 当k==2时，我们枚举数组两两想减，得到新的数字，假设是数组b； 这样我们就有[a1, a2, a3... an] 和 [b1, b2, b3...bn]两个数组； 这样只需要再枚举数组a和数组b相减，得到数组c； 最小值就是数组a、b、c中的最小值。
这样的复杂度，首先是数组b的生成，O(N^2)，最多会生成1e6个数字； 最后再枚举生成c的时候，复杂度就达到了O(N^3），最终复杂度超标。
重新审视问题分析过程，当k==1时，其实不需要所有数字两两相减，举一个例子： 当数组为[9,7,5,1]，当枚举9与其他数字的差值时，只需要考虑[9,7]的情况，也就是整个数组其实只需要考虑3个情况[9, 7] 、[7,5]、[5,1]； 这里的前提，是数组是有序的。可以对数组进行排序，复杂度是O(NlogN），接下来枚举复杂度就是O(N）； 但是，当k==2时，是否可以继续只考虑相邻数字呢？ 是不可以的，因为相邻数字想减，生成的只是当前最小，不意味着再一次操作的更小，比如说[9,7,5,4]，第一次无法生成9-5=4，那么第二次操作就无法归零。 所以首次操作，需要生成N^2个数字的数字b； 在第二次操作的时候，我们会从数组a选择1个数字，再从数组b选择1个数字，此时可以参考k=1的时候的做法，将数组b排序，对于每个数字a[i]，我们只需要考虑数组b中离a[i]数字最接近的数字。 此时可以用二分法，在数组b中寻找。但是我们有更简单的做法： 将数组a和数组b一起排序，然后对于a[i]，我们就往左右遍历，这样就能更方便去找到数字。
typedef long long lld;
class Solution {
static const int N = 4010100;
lld a[N];
pair<lld, lld> b[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; ++i) cin >> a[i];
sort(a, a + n);
if (k >= 3) {
cout << 0 << endl;
}
else if (k == 2) {
int cnt = 0;
for (int i = 0; i < n; ++i) {
b[cnt].first = a[i];
b[cnt].second = 0;
cnt++;
}
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
b[cnt].first = abs(a[i] - a[j]);
b[cnt].second = 1;
++cnt;
}
}
sort(b, b + cnt);
lld ans = a[0];
for (int i = 0; i < cnt; ++i) {
ans = min(ans, b[i].first);
if (b[i].second == 0) { // 数组a来匹配最近的一个数字
int x = i, y = i;
while (x > 0) {
--x;
if (b[x].second == 1) break;
}
while (y < cnt - 1) {
++y;
if (b[y].second == 1) break;
}
if (x != i) {
ans = min(ans, abs(b[i].first - b[x].first));
}
if (y != i) {
ans = min(ans, abs(b[i].first - b[y].first));
}
}
}
cout << ans << endl;
}
else if (k == 1) {
lld ans = a[0];
for (int i = 1; i < n; ++i) ans = min(ans, min(a[i], a[i] - a[i - 1]));
cout << ans << endl;
}
}
}
}
ac;题目4
题目链接 题目大意： 给出n个整数的数组a和b，现在可以对数组a进行操作： 选择数组内任意区间[l, r]，将区间[l, r]内的整数都改为区间的最大值。 比如，对于数组[1, 2, 3, 4, 5]，选择区间[1, 3]进行操作，则会生成[3, 3, 3, 4, 5]；
现在想知道，数组a是否可以进行若干次上面的操作，最终变成数组b。
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例3行 第1行整数 n (1≤n≤1000) 第2行整数 𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤𝑛) 第3行整数 𝑏1,𝑏2,…,𝑏𝑛 (1≤𝑏𝑖≤𝑛)
输出： 每个样例一行，如果可行则输出YES，如果不可行则输出NO；
Examples input 5 5 1 2 3 2 4 1 3 3 2 4 5 3 4 2 2 4 3 4 3 4 4 5 3 2 1 1 1 3 3 3 2 2 2 1 1 1 2 3 1 1 2 2 1 2
output YES NO YES NO NO
题目解析： 从数据量较小的情况开始分析，比如说n=2时，数组数字可以简化成1和2； 那么就会有[1,2]和[2,2]，比较容易得到结果； 当n=3时，我们增加个数组3，如果放在数组[1,2]左右两边，对结果不影响；但是如果放在中间，数组[1, 3, 2]是无法变成[2, 3, 2]； 由此我们可以知道，较大的数字会阻断较小的数字传递； 当n=4时，我们可以看到一个有意思的样例： 1,2,3,4 3,4,4,4 数字3，跨过第2个数字影响到了第1个数字，然后第2、3个数字最终又被数字4覆盖。 由此我们可以知道，数字的影响是最终可能非间隔，但是必须传递过去，并且中间路径可能被更大数字覆盖。
至此，我们的思路就清晰起来： 1、从小到大来枚举数字，因为当x覆盖过某个数字后，只有x+1才能覆盖这个覆盖； 2、每一个数字，都可以向左右蔓延，蔓延条件有两个，隔壁数字小于等于当前数字，隔壁数字对应的数组b元素要大于等于当前数字； 3、重复上面所有的过程，直到所有数字结束；
这里的核心依据，就是通过数组b的元素作为数组a元素的上限，尽可能让每一个数组a元素去变大。
思考： 当N的范围再扩大1000倍呢？上面的这个做法在效率上就会不足，但是思路可以沿用扩展。 首先回顾这里的耗时操作，首先是枚举数字从小到大，然后找到和这个位置对应的数字，简单实现是O（N^2）的复杂度，但是我们先预处理一遍数组，记录每个数字对应的下标，这样就可以做到O（N）的复杂度； 其次是在数字覆盖的过程中，有时会出现每个位置被重复覆盖多次的情况，但是对于结果而言，我们只需要知道某个位置不匹配时（a[i] != b[i]），它应该往数组a左边/右边去找到等于b[i]的元素。 这个过程，同样可以预处理。 比如说对于下面的样例，当a[3] != b[3]，我们要往数组a两边去找数组元素等于3的情况； 3 3 2 1 4 3 3 3 3 3 3 4 3 3 首先在前面的预处理步骤，我们记录每一个数字的位置，那么对于数字3，我们同样记录了3在数组a的位置为[0,1,5,6]，这样我们很容易知道对于a[3]而言，最近数字3位置在a[1]和a[5]；
接下来的问题是，对于某个位置i和某个位置j，是否能够匹配？ 还是用上面的样例，我们才用采样这样的策略： 1、对于数组a，我们从小到大枚举的元素的过程，我们把枚举过的数字（包括当前数字），在数组a出现的位置都用1来标明；（某个位置为1，表示该位置可以延伸） 2、对于数组b，我们从小到大枚举的元素的过程，我们把还没有枚举过的数字（包括当前数字），在数组b出现的位置都用1来标明；（某个位置为1，表示该位置可以延伸） 样例数据 3 3 2 1 4 3 3 3 3 3 3 4 3 3 就可以转义为 1 1 1 1 0 1 1 1 1 1 1 1 1 1 这样， 当我们在判断a[1]和a[3]是否能够匹配时，其实就是判断数组a区间[1, 3]的数字和是否为3，并且数组b区间[1,3]的数字和是否为3；
那么如何做快速的标记、以及计算累加和呢？ 1、标记问题，通过预处理我们能O(1)获取对应位置，并且每个数字我们只会标记一次，所以总的标记复杂度是O(N)； 2、计算累加和，在一个数组里面，可以对某些元素进行数值修改、然后要求区间和，可以用线段树来解决。
class Solution {
static const int N = 201010;
int a[N], b[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i < n; ++i) cin >> b[i];
for (int k = 1; k <= n; ++k) {
for (int i = 0; i < n; ++i) {
if (a[i] == k) {
int x = i - 1, y = i + 1;
while (x >= 0 && a[x] <= k && k <= b[x]) {
a[x] = k;
--x;
}
while (y < n && a[y] <= k && k <= b[y]) {
a[y] = k;
++y;
}
}
}
}
int ans = 1;
for (int i = 0; i < n; ++i) ans = ans && (a[i] == b[i]);
cout << (ans ? "YES" : "NO") << endl;
}
}
}
ac;题目5
题目链接 题目大意： 有n个正整数的数组a，现在Alice和Bob在玩游戏，Alice先操作，Bob再操作； Alice会移除数组中，最多k个元素； Bob会将数组中，最多x个元素乘以-1；
每个人只行动一次，Alice想要让最终数组的元素和尽可能大，Bob想要让数组的元素和尽可能小； 问最终的数字和为多少；
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例2行 第一行，整数𝑛 , 𝑘 , and 𝑥 (1≤𝑛≤2⋅1e5 , 1≤𝑥,𝑘≤𝑛 ) 第二行，n个整数𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤1000)
输出： 每个样例一行，输出最终的数字和；
Examples input 8 1 1 1 1 4 1 1 3 1 2 4 6 6 3 1 4 3 2 5 6 6 6 1 3 7 3 3 32 15 8 5 3 5 5 3 3 3 2 9 9 10 6 4 1 8 2 9 3 3 4 5 3 200 2 2 1 4 3 2 1 2 1 3
output 0 2 0 3 -5 -9 0 -1
题目解析： 由于题目有k和x两个变量，我们先考虑x=1个数字的情况； 假设题目数据已经从大到小排序，数组还是a，以4、3、2、1为例； 先考虑bob的操作（为什么是先考虑后手？因为这样思考简单） 假设Alice没有操作，那bob一定会选择-4，也就是数组最大的元素；（如果x=2，那么就是前2个）
那么Alice如果操作呢？ 移除4的好处是最终消除了-4，但是增加了-3，同时移除原来正数3，总体的代价应该是4-3-3=-2，所以Alice不操作结果更佳；
由此可知道数组排序后，Alice如果移除，一定是移除前面若干个数字；Bob的负数操作，也一定是前面x个数字。 那么只需要枚举下k=0、1、2、3、、、k的情况，对应的结果。（边界情况比较容易些错，可以直接模拟，简化过程）
注意： 一些特殊case k=2, x=2 4+3+2+1 -4-3+2+1=-4 -3-2+1=-4 -2-1=-3
k=2, x=2 6+6+3.5+1 -6-6-+4.5=-7.5 -3.5-1=-4.5
typedef long long lld;
class Solution {
static const int N = 201010;
lld a[N], sum[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, k, x;
cin >> n >> k >> x;
for (int i = 0; i < n; ++i) cin >> a[i];
sort(a, a + n, greater<int>());
sum[0] = a[0];
// [left, mid, right]
// left是移除，mid是负数，right是剩下
lld leftSum = 0, midSum = 0, rightSum = 0;
for (int i = 0; i < x; ++i) midSum += a[i];
for (int i = x; i < n; ++i) rightSum += a[i];
lld ans = rightSum - midSum;
for (int remove = 1; remove <= k; ++remove) {
midSum -= a[remove - 1]; //移除当前这个数字
if (remove + x <= n) {
// 右边还有剩余
midSum += a[remove + x - 1]; // midSum增加这个数字
rightSum -= a[remove + x - 1]; // rightSum移除这个数字
}
ans = max(ans, rightSum - midSum);
}
cout << ans << endl;
}
}
}
ac;