题目分析

问题重述

我们需要找到最小的非负整数 $m$，使得存在 $m$ 天的调整 $(x_i', y_i')$ 满足：

1. $\sum_{i=0}^{m-1} (x_i' + x_{i \bmod n}) = x$
2. $\sum_{i=0}^{m-1} (y_i' + y_{i \bmod n}) = y$
3. $\forall i, |x_i'| + |y_i'| \leq k$

关键观察

设：

• $S_x = \sum_{i=0}^{m-1} x_i'$（调整量的x总和）
• $S_y = \sum_{i=0}^{m-1} y_i'$（调整量的y总和）
• $T_x = \sum_{i=0}^{m-1} x_{i \bmod n}$（固定风力的x总和）
• $T_y = \sum_{i=0}^{m-1} y_{i \bmod n}$（固定风力的y总和）

则条件可重写为：

• $S_x + T_x = x$
• $S_y + T_y = y$
• 每天调整量满足曼哈顿距离约束

解法思路

数学推导

设 $m = qn + r$，其中 $0 \leq r < n$，则：

$$T_x = q \cdot \sum_{i=0}^{n-1} x_i + \sum_{i=0}^{r-1} x_i $$$$T_y = q \cdot \sum_{i=0}^{n-1} y_i + \sum_{i=0}^{r-1} y_i $$

令：

• $X = \sum_{i=0}^{n-1} x_i$
• $Y = \sum_{i=0}^{n-1} y_i$
• $X_r = \sum_{i=0}^{r-1} x_i$
• $Y_r = \sum_{i=0}^{r-1} y_i$

则：

$$T_x = qX + X_r$$ $$T_y = qY + Y_r$$

我们需要：

$$S_x = x - T_x = x - qX - X_r$$ $$S_y = y - T_y = y - qY - Y_r$$

调整量的约束

由于每天调整量满足 $|x_i'| + |y_i'| \leq k$，那么 $m$ 天的总调整量满足：

$$|S_x| + |S_y| \leq mk$$

因此必要条件为：

$$|x - qX - X_r| + |y - qY - Y_r| \leq mk = k(qn + r) $$

算法框架

对于每个余数 $r$（$0 \leq r < n$），我们需要找到最小的 $q \geq 0$ 使得：

$$|x - qX - X_r| + |y - qY - Y_r| \leq k(qn + r)$$

然后取所有 $(q, r)$ 组合中的最小值 $m = qn + r$。

代码实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll INF = 1e18;

ll n, k, x, y;
vector<ll> xs, ys;
vector<ll> preX, preY;  // 前缀和

// 检查对于给定的q和r是否满足条件
bool check(ll q, ll r) {
    ll total_days = q * n + r;
    ll total_X = q * preX[n] + preX[r];  // T_x
    ll total_Y = q * preY[n] + preY[r];  // T_y
    
    ll S_x = x - total_X;  // 需要的调整量x总和
    ll S_y = y - total_Y;  // 需要的调整量y总和
    
    // 检查曼哈顿距离约束
    return abs(S_x) + abs(S_y) <= k * total_days;
}

ll solve() {
    cin >> n >> k >> x >> y;
    xs.resize(n);
    ys.resize(n);
    
    for (int i = 0; i < n; i++) {
        cin >> xs[i] >> ys[i];
    }
    
    // 计算前缀和
    preX.resize(n + 1);
    preY.resize(n + 1);
    preX[0] = preY[0] = 0;
    for (int i = 0; i < n; i++) {
        preX[i + 1] = preX[i] + xs[i];
        preY[i + 1] = preY[i] + ys[i];
    }
    
    ll total_X = preX[n];  // X
    ll total_Y = preY[n];  // Y
    
    ll ans = INF;
    
    // 枚举余数r
    for (ll r = 0; r <= n; r++) {
        // 二分查找最小的q
        ll left = 0, right = 2e8;  // 设置足够大的上界
        ll best_q = INF;
        
        while (left <= right) {
            ll mid = (left + right) / 2;
            if (check(mid, r)) {
                best_q = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        if (best_q != INF) {
            ans = min(ans, best_q * n + r);
        }
    }
    
    return ans == INF ? -1 : ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin >> T;
    while (T--) {
        cout << solve() << "\n";
    }
    
    return 0;
}

优化分析

上述代码对于每个测试数据是 $O(n \log A)$ 的，其中 $A$ 是 $q$ 的上界。但 $n$ 最大为 $10^5$，$T$ 最大为 $5 \times 10^4$，总 $n$ 为 $10^6$，可能仍然会超时。

数学优化

观察不等式：

$$|x - qX - X_r| + |y - qY - Y_r| \leq k(qn + r)$$

这可以重写为：

$$|A - qX| + |B - qY| \leq kqn + C$$

其中 $A = x - X_r$, $B = y - Y_r$, $C = kr$

对于固定的 $r$，这是一个关于 $q$ 的不等式。我们可以分析函数 $f(q) = |A - qX| + |B - qY| - kqn$ 的行为。

更高效的实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll INF = 4e18;  // 需要更大的上界

ll n, k, x, y;
vector<ll> xs, ys;
vector<ll> preX, preY;

// 计算对于给定q和r的曼哈顿距离
ll calc_manhattan(ll q, ll r) {
    ll total_X = q * preX[n] + preX[r];
    ll total_Y = q * preY[n] + preY[r];
    return abs(x - total_X) + abs(y - total_Y);
}

ll solve_optimized() {
    cin >> n >> k >> x >> y;
    xs.resize(n);
    ys.resize(n);
    
    for (int i = 0; i < n; i++) {
        cin >> xs[i] >> ys[i];
    }
    
    preX.resize(n + 1);
    preY.resize(n + 1);
    preX[0] = preY[0] = 0;
    for (int i = 0; i < n; i++) {
        preX[i + 1] = preX[i] + xs[i];
        preY[i + 1] = preY[i] + ys[i];
    }
    
    ll total_X = preX[n];
    ll total_Y = preY[n];
    
    ll ans = INF;
    
    // 特殊情况：m = 0
    if (x == 0 && y == 0) {
        ans = 0;
    }
    
    // 枚举余数r
    for (ll r = 0; r <= n; r++) {
        if (r == n) r = 0;  // r从0到n-1
        
        ll base_manhattan = abs(x - preX[r]) + abs(y - preY[r]);
        
        // 如果总风量为0，需要特殊处理
        if (total_X == 0 && total_Y == 0) {
            if (base_manhattan <= k * r) {
                ans = min(ans, r);
            }
            continue;
        }
        
        // 二分查找q
        ll left = 0, right = 4e8;
        while (left <= right) {
            ll mid = left + (right - left) / 2;
            ll manhattan_dist = calc_manhattan(mid, r);
            ll total_days = mid * n + r;
            
            if (manhattan_dist <= k * total_days) {
                ans = min(ans, total_days);
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
    }
    
    return ans == INF ? -1 : ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin >> T;
    while (T--) {
        cout << solve_optimized() << "\n";
    }
    
    return 0;
}

特殊情况处理

1. $m = 0$：当 $x = 0$ 且 $y = 0$ 时，答案可能是0
2. 总风量为0：当 $X = 0$ 且 $Y = 0$ 时，问题简化为检查单个周期
3. $k = 0$：此时每天调整量必须为0，问题有特殊性质

复杂度分析

• 时间复杂度：$O(n \log A)$ 每个测试数据，其中 $A$ 是 $q$ 的上界
• 空间复杂度：$O(n)$
• 总复杂度：$O(\sum n \log A)$，在约束范围内

算法总结

1. 问题转化：将原问题转化为寻找满足不等式的最小 $m$
2. 周期分解：将 $m$ 分解为 $qn + r$ 的形式
3. 二分答案：对于每个余数 $r$，二分查找最小的 $q$
4. 曼哈顿距离：使用绝对值不等式作为约束条件

这道题的关键在于将复杂的约束条件转化为数学不等式，然后利用二分查找高效求解。