算法 不等式 | 同余 + 破换成链

给定 𝑛 个整数 ℎ𝑖，每次操作会使 ℎ𝑖←ℎ𝑖+𝑎𝑖，求能否在若干次操作后使得 ℎ𝑖 的排名（从大到小）为 𝑡𝑖+1(就是前面有ti个)，如果可以，求最小操作次数，否则输出-1。

这个关键在维护一个区间集, 利用给出的目标排名确定不等式, 每个不等式成立都会给出一个区间, 然后加到这个区间集中

最后得到的区间集如果成立, 就是符合所有不等式的答案

• 设经过的天数为x

• 不等式中按照顺序每个不等式都是这样的形式 : h1 + x * a1 > h2 + x * a2

• 可以转化为 : x < (h1 - h2) / (a2 - a1)

• 于是就要判断a2 - a1, 是否大于0 :

  • > 0 : x < (h1 - h2) / (a2 - a1) , 小于缩右区间.

  • < 0 : x > (h1 - h2) / (a2 - a1), 大于缩左区间.

  • = 0 : 这时比较h1和h2, 如果h1 > h2, 则 x * 0 < (h1 - h2)永远成立, 如果h1 < h2, 则x * 0 < (h1 - h2)永远无解.

    无解的话则排名不可能实现, 直接退出就行.

#include<iostream>
#include<cmath>
#define rep(i,a,b) for(int i = (a); i <= (b); i ++ )
using namespace std;
const int N = 200010;
int n; 
int h[N], a[N], rk[N];

void solve()
{
    cin >> n;
    rep(i, 1, n) cin >> h[i];   // 高度
    rep(i, 1, n) cin >> a[i];   // 增量
    rep(i, 1, n)                
    {
        int w;
        cin >> w;
        rk[w + 1] = i;  // i目标的目标排名
    }
    
    int l = 0, r = 1e9;
    rep(i, 1, n - 1)
    {
        int A = h[rk[i]] - h[rk[i + 1]];
        int B = a[rk[i + 1]] - a[rk[i]];
        // 我们对于边界只取整数
        // x < w -> x <= ceil(w) - 1  (x < 1.1 -> x <= 1)
        if(B > 0) r = min(r, (int)ceil((double)A / B) - 1);
        // x > w -> x >= floor(w) + 1  (x > 1.1 -> x >= 2)
        else if(B < 0) l = max(l, (int)floor((double)A / B) + 1);
        else if(A <= 0)
        {
            r = -1;
            break;
        }
    }
    if(l <= r) cout << l << endl;
    else cout << -1 << endl;
}

int main()
{
    int t;
    cin >> t;
    while(t -- )
    {
        solve();
    }
}

---

给定一个序列 𝑎𝑖，每次操作可以让序列中一个元素加一或者减一，求让所有元素减去某个数 𝑥 之后可以被 𝑚 整除的最小操作数。

这道题的关键在于整除可以转化为同余关系, 在同余下对元素的加减一可以被视为一个循环.

由题可得, a - x ≡ 0 (mod m) , 所以a ≡ x(mod m).

现在问题就转化为了求使ai全部变成x要的最小操作数.

这种问题有常规解法, 就是排序取中位数, 然后两边可以用前缀和求.

但这道题是建立在同余的前提下的, 我们其实无法准确判断中位数到底是哪个, 因为每个a的循环的, 到达同一个数可以是加也可以是减, 所以我们无法按照中位数的来决定每个a必定是加还是减.

于是我们就要遍历每个点, 把每个点都当作中位数进行一次判断, 这种操作在长度为n的数组的中很难实现, 所以可以把数组复制到后面, 使长度变成2n, 这样就可以固定一定区间长度, 移动区间来进行判断.

#include <iostream>
#include <algorithm>
#include <vector>
#define int long long
#define rep(i, a, b) for(int i = (a); i <= (b); i ++ )
using namespace std;
const int N = 200010;

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(2 * n + 10);
    rep(i, 1, n) cin >> a[i], a[i] %= m; // 由于a和x同余m, 所以可以先都 % m
    sort(a.begin() + 1, a.begin() + n + 1);
    // 破环成链
    // 这里至于为什么加m, 其实比较模糊
    // 可以理解为是为了保证a升序, 之后的前缀和计算可以正确进行
    // 我的感觉就是由于所有a都是在0到m-1之间循环, 虽然不确定在正确答案中是向上加还是向下减, 
    // 但是还是一定只有两个方向, 这样复制数组再整体加m的做法其实就是促成一个加一个减.
    rep(i, n + 1, 2 * n) a[i] = a[i - n] + m;
    // 记录前缀和
    vector<int> pre(2 * n + 10);
    rep(i, 1, 2 * n) pre[i] = a[i] + pre[i - 1];
    int ans = 1E18;
    // 枚举环上每个点
    rep(i, 1, n)
    {
        int l = i, r = i + n - 1;
        int mid = (l + r + 1) / 2;
        int res;
        if (n % 2 == 0) {
            // 偶数的时候，[mid, r] - [l, mid - 1];
            res = pre[r] - 2 * pre[mid - 1] + pre[l - 1];
        } else {
            // 奇数的时候，[mid + 1, r] - [l, mid - 1]; 
            res = pre[r] - pre[mid] - pre[mid - 1] + pre[l - 1];
        }
        ans = std::min(ans, res);
    }
    cout << ans << endl;
}

signed main()
{
    int t;
    cin >> t;
    while(t -- )
    {
        solve();
    }
    return 0;
}