A. Array Balancing

Code

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)	cin >> a[i];
    for (int i = 1; i <= n; i++)	cin >> b[i];
    
    int res = 0;
    for (int i = 1; i < n; i++)
        res += min(abs(a[i] - a[i + 1]) + abs(b[i] - b[i + 1]), abs(a[i] - b[i + 1]) + abs(b[i] - a[i + 1]))
    	
    cout << res << endl;
}

B. Getting Zero（位运算）

题目大意

解题思路

Code

void solve()
{   
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int res = 0x3f3f3f3f;
        int x;  cin >> x;
        for (int i = 1; i <= 15; i++)
        {
            int t = ((1 << i) - 1) & x;  // 如从10000变为01111, &之后可以得到另一个数字的后四位大小
            int k;  //  +1的次数
            if (t == 0) k = 0;  // 特判，如果x本身就是0的话，不需要加1
            else k = (1 << i) - t;
            res = min(res, 15 - i + k);  //15 - i是*2的次数  *2 相当于左移一位
        }
        cout << res << ' ';
    }
}

C. Water the Trees (分类讨论)

题目大意

有若干棵树,奇数天可以浇水让一棵树长高$1$个单位,偶数天可以浇水让一棵树长高$2$个单位,问最少多少天可以让所有数长得一样高.

解题思路

假设我们已经知道了最终树要长多高,我们可以统计一下每棵树要长高的高度,我们发现要长高的高度为奇数的树至少需要一次在奇数天浇水,而要长高的高度为偶数的树无所谓.所以我们统计要长高的高度为奇数的树的数目$cnt$.出现$cnt$次奇数天最少需要$2 * cnt - 1$天.然后我们再统计以下一共需要长高的高度,计算需要的总天数和前面的值比较取大即可.

假设所有树初始高度中最大值为$maxv$,另外一个要注意的点是所有树最终高度的取值只有可能是$maxv$和$maxv + 1$,取$maxv + 1$有可能可以通过减少奇数天数的数量来降低答案,所以两个高度分别计算取小即可.

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 300030;

int n, a[N];

int solve(int maxv)
{
    int sum = 0, cnt = 0;   // cnt表示奇数的数量
    for (int i = 1; i <= n; i++)
    {
        int d = maxv - a[i];
        sum += d;
        if (d & 1)  cnt++;
    }

    int res = 0;
    if (sum % 3 == 0)   res = max(2LL * cnt - 1, sum / 3 * 2);
    else if (sum % 3 == 1)  res = max(2LL * cnt - 1, sum / 3 * 2 + 1);
    else res = max(2LL * cnt - 1, sum / 3 * 2 + 2);  //  再等到一个偶数天需要先经过一个奇数天
    
    return res;
}

signed main()
{
    int t;  cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)    cin >> a[i];
        int maxv = *max_element(a + 1, a + 1 + n);
        cout << min(solve(maxv), solve(maxv + 1)) << endl; // 不可能是（maxv+2)天，因为全体+2的操作可以被撤回
    }
}