题目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;