程序员进阶之算法练习（六十七）
题目1
题目链接 题目大意： 给出n个整数的数组a和b，现在可以执行任意次下面的操作： 选择索引x，交换数组a和b中的元素a[x]和b[x]；
现在想知道|𝑎1−𝑎2|+|𝑎2−𝑎3|+⋯+|𝑎𝑛−1−𝑎𝑛| + |𝑏1−𝑏2|+|𝑏2−𝑏3|+⋯+|𝑏𝑛−1−𝑏𝑛| 的最小值是多少；
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤4000) 每个样例3行，第一行整数 𝑛 (2≤𝑛≤25) 第二行n个整数 𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤1e9) 第三行n个整数 𝑏1,𝑏2,…,𝑏𝑛 (1≤𝑏𝑖≤1e9)
输出： 每个样例一行，输出最小值；
Examples input 3 4 3 3 10 10 10 10 3 3 5 1 2 3 4 5 6 7 8 9 10 6 72 101 108 108 111 44 10 87 111 114 108 100 output 0 8 218
题目解析： 假设有数字a1和a2，b1和b2； 在一个一维数轴上，a1和b1就是两个点，并且我们可以让a1<b1； 然后 |a1-a2|+|b1-b2| 其实就是在数轴上还有两个点a2和b2，也可以让a2<b2； 题目的要求，就是求（a1到a2距离+b1到b2距离） 和 （a1到b2距离+b1到a2的距离）哪个距离和更小； 可以知道，还是前者的距离更小，因为后者中的a1到b2距离 或者 b1到a2的距离，总会有一个距离很大；
也可以用简单的思维来看：小的和小的比，大的和大的的比。
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];
if (a[i] > b[i]) {
swap(a[i], b[i]);
}
}
lld sum = 0;
for (int i = 0; i < n - 1; ++i) {
sum += abs(a[i] - a[i + 1]);
sum += abs(b[i] - b[i + 1]);
}
cout << sum << endl;
}
}
}
ac;题目2
题目链接 题目大意： 给出一个整数v，现在可以执行任意次操作： 𝑣 = (𝑣+1) mod 32768 或 𝑣 = (2⋅𝑣) mod 32768.
现在想知道，最少执行多少次操作，才能让整数变成0；
输入： 第一行整数𝑛 ，表示n个整数(1≤𝑛≤32768) 第二行n个整数𝑎1,𝑎2,…,𝑎𝑛 (0≤𝑎𝑖<32768)
输出： 输出n个整数，分别表示n个整数的最少操作次数。
Examples input 4 19 32764 10240 49 output 14 4 4 15
题目解析： 32768是一个比较大的整数，由于操作里面有一个乘以2操作，我们将32768进行除以2操作，发现32768=2^15； 那么如果将整数v当成一个二进制数，就是寻求如何快速将这个二进制数的后面15位变为0；
那么+1就是在整数末尾+1，如果是乘以2就是将整个整数左移； 最极端的情况，将整个整数左移15次，一定会有解； 另外，容易知道如果执行过一次x2操作，就不会再执行+1操作，因为x2操作是末尾补0，但是+1会导致末尾变成1； 那么问题就变成在x2之前，需要执行多少次+1操作；
这里有很多种做法：枚举x2操作的次数，然后计算剩下所有加法次数； 枚举+1的次数，再计算枚举x2的次数；
class Solution {
static const int N = 201010;
int a[N], b[N];
void check(int n) {
char s[20];
int pos = 0;
while (n) {
s[pos++] = '0' + n % 2;
n /= 2;
}
reverse(s, s + pos);
s[pos] = 0;
cout << s << endl;
}
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
if (n == 0) {
cout << 0 << endl;
continue;;
}
int ans = 15; // 1 << 15
// check(n);
for (int i = 0; i < 15; ++i) {
int mod = 1 << (15 - i);
int left = n % mod;
ans = min(ans, i + (mod - left) % mod);
}
cout << ans << endl;
}
}
}
ac;题目3
题目链接 题目大意： 有n个整数，现在可以执行若干次操作，每次操作可以选择数组中某个元素进行增长，也可以选择跳过该操作； 这样进行第1次操作、第2次操作、第3次操作.... 假如第1、2、3次操作中，第k次操作是选择数组元素a[i]，则如果k是奇数则使a[i]=a[i]+1；如果k是偶数则使a[i]=a[i]+2；
现在想知道，最好经过多少次操作可以让整个数组的元素相等。
输入： 第一行整数𝑡，表示t个样例 (1≤𝑡≤2⋅1e4) 每个样例2行，第一行是整数 𝑛 (1≤𝑛≤3⋅1e5) 第二行是整数 ℎ1,ℎ2,…,ℎ𝑛 (1≤ℎ𝑖≤1e9)
输出： 每个样例一行，最少的操作数。
Examples input 3 3 1 2 4 5 4 4 3 5 5 7 2 5 4 8 3 7 4 output 4 3 16
题目解析： 目标是所有整数一样，那么假设maxItem是数组中最大的元素，最终的结果必然是maxItem或者maxItem+1； 证明：可以用反证法，假如最终结果是maxItem+2，那么必然可以将所有整数-2（或者连续-1两次），得到最终元素maxItem。
现在问题就变成，假如n个元素都要变成maxItem，最少需要多少次操作。 根据对于第i个元素a[i]，我们得到diff=maxItem-a[i]； 如果diff是偶数，那么需要diff/2次+2操作；如果diff是奇数，那么需要diff/2次+2操作和1次+1操作； 我们用odd表示+1操作次数，event表示+2操作次数，根据上面的规则，我们可以算出来总的odd和even。
接下来考虑替换的问题，假如even比odd大，那么存在一种替换关系： 两个+1操作可以替换成1个+2操作； 那么我们用tmp = (even - odd)/3，可以得到tmp次无缝替换；（为什么要/3？以为在把+2替换成+1的时候，+2的数量也会-1）
这样令odd = odd + tmp * 2, even = even - tmp，得到无法替换的odd和even次数； 此时还存在一种特殊情况，就是even - odd = 2的情况： 此时仍然1个+2可以替换成2个+1，整体的代价为1。 比如说样例 3 1 1 3 odd=0，even=2，如果不做任何替换，则ans=even*2=4； 但是可以把1个+2替换成2个+1，此时odd=2, even=1,此时ans = odd * 2 - 1 = 3;
得到最终的odd和even数量后，就可以得到答案： 如果odd>even, 则 ans = odd * 2 - 1; 如果odd<=even，则 ans = even * 2；
注意：题目需要用long long来处理，避免整数溢出；以及整体数据量偏大，注意数组边界，避免越界；
class Solution {
static const int N = 301010;
lld a[N];
lld check(lld n, lld maxItem) {
lld ans = 0;
lld odd = 0, even = 0;
for (int i = 0; i < n; ++i) {
lld diff = maxItem - a[i];
even += diff / 2;
if (diff % 2) {
odd += 1;
}
}
// cout << "max:" << maxItem << " odd: " << odd << " even: " << even << " ans: " << ans << endl;
// 接下来就是将多余的even拆成odd来实现
// (even - odd) / 3 这部分是一定可以拆的
if (even > odd && (even - odd) / 3) {
lld tmp = (even - odd) / 3;
odd += tmp * 2;
even -= tmp;
}
if (even == 0 && odd == 0) {
ans = 0;
}
if (odd > even) {
ans = odd * 2 - 1;
}
else {
if (even - odd == 2) {
ans = even * 2 - 1;
}
else {
ans = even * 2;
}
}
return ans;
}
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
lld maxItem = 0;
for (int i = 0; i < n; ++i) {
cin >> a[i];
maxItem = max(maxItem, a[i]);
}
cout << min(check(n, maxItem), check(n, maxItem + 1)) << endl;
}
}
}
ac;题目4
题目链接 题目大意： 有n个整数，现在可以执行若干次操作，每次操作可以选择数组中某个元素进行增长，也可以选择跳过该操作； 这样进行第1次操作、第2次操作、第3次操作.... 假如第1、2、3次操作中，第k次操作是选择数组元素a[i]，则如果k是奇数则使a[i]=a[i]+1；如果k是偶数则使a[i]=a[i]+2；
现在想知道，最好经过多少次操作可以让整个数组的元素相等。
输入： 第一行整数𝑡，表示t个样例 (1≤𝑡≤2⋅1e4) 每个样例2行，第一行是整数 𝑛 (1≤𝑛≤3⋅1e5) 第二行是整数 ℎ1,ℎ2,…,ℎ𝑛 (1≤ℎ𝑖≤1e9)
输出： 每个样例一行，最少的操作数。
Examples input 3 3 1 2 4 5 4 4 3 5 5 7 2 5 4 8 3 7 4 output 4 3 16
题目解析： 把每次操作都当成是选择一个线段，那么最终会有m个线段，我们关注每个线段右边终点； 然后从右到左遍历数组元素，对于第i个元素，尽可能使得元素i满足a[i]>=b[i]，这样一定会有最优解。 这里的证明比较明显，比如线段[i, j]对于元素j肯定是最优解，[i+1, j+1]会浪费j+1部分，[i-1, j-1]则会无法增加j的大小。
但是按照上的做法，每个元素都要遍历元素i和前面k个元素，总体的复杂度是O(NK)，会出现超时的情况。 但是对于已经给定的某个线段数量，我们能在O(N)的时间判断这个是否有解，配合数量的二分，可以在O(NLogM）的复杂度内得到结果，M是最大的结果。
对于mid条线段，我们先假设全部添加在元素i上面，然后每次计算元素i上面有多少条线段可以左移1位，这个数字就是(a[i]-b[i])/k； 然后不断计算这个移动的过程，直到线段无法移动（如果移动之后a[i]会小于b[i]，则这个位置无法移动线段）； 对于元素i，初始化的时候添加mid条线段的复杂度是O(K)，接下来每次移动一条线段都可以用c[i-k-1] -= 1和c[i-1] += 1来标记，后面就需要根据初始化的值以及这个区间内c的大小来得到结果；
思考🤔： 是否有最优解呢？ 有的，理论最优解应该是O（N），从最初的贪心做法开始分析，最大的重复计算是每次操作之后，进行区间计算的过程。 这个计算有明显的线性特性，可以进行如下的优化： 对于数组[1, 3, 4, 7]来说，当我们在最后添加3条线段的时候，我们会得到[0, 3, 6, 9]，但是需要计算3次，这也是复杂度超标的所在。 接着上面的思路，当我们在第4个元素选择添加3条线段时，我们令a[3]=9，同时记录sum=9，cnt=3，并且用上面的区间标记方式，在c[2]和c[0]的地方标记+3和-3； 这样当我们访问第3个元素时，我们只需要计算sum-cnt，就可以快速得到之前的结果，并且根据c的信息实时更新cnt的大小即可。 这样只需要遍历一次数组，并且每次操作都是O(1)，达到了理论最优解O(N)；
class Solution {
static const int N = 301010;
lld a[N], b[N], c[N], n;
bool check(lld k, lld mid) {
for (lld i = 0; i <= n; ++i) {
a[i] = c[i] = 0;
}
for (lld i = 0; i < k; ++i) {
a[n - k + i] = mid * (i + 1);
}
lld cur = mid, seg = 0; // 当前有cur条线段以i结束，仅有这部分可以左移
for (lld i = n - 1; i >= 0; --i) {
seg += c[i];
// cout << mid <<" " << i << " " << a[i] + seg << endl;
if (a[i] + seg < b[i]) {
return false;
}
lld move = min(cur, (a[i] + seg - b[i]) / k);
cur = move;
if (i >= k) {
c[i - 1] += move;
}
if (i >= k + 1) {
c[i - k - 1] -= move;
}
}
return true;
}
public:
void solve() {
lld t = 1;
while (t--) {
lld k;
cin >> n >> k;
lld top = 0;
for (lld i = 0; i < n; ++i) {
cin >> b[i];
}
for (lld i = 0; i < n; i+=k) {
lld tmp = 0;
for (lld j = 0; j < k; ++j) {
tmp = max(tmp, b[i + j]);
}
top += tmp;
}
lld left = 1, right = top + 1;
lld ans = right;
while (left <= right) {
lld mid = (left + right) / 2;
if (check(k, mid)) {
ans = mid;
right = mid - 1;
}
else {
left = mid + 1;
}
}
cout << ans << endl;
}
}
}
ac;腾讯云开发者
