【2026/01/08】每日一题解析

问题解答

1. 关于题目一（数组最大值）的思考

• 优先队列的时间复杂度是多少？
  • 构建初始堆为 $O(N)$。
  • 每次操作涉及弹出和压入，复杂度为 $O(\log N)$。
  • 总时间复杂度为 $O(K \log N)$。
  • 结论：在 $N=10^5, K=2 \times 10^5$ 时，计算量约 $3.6 \times 10^6$，远低于 $10^8$ 的限制，可以通过。
• 如果 $K$ 最大值为 $10^{10}$，优先队列是否会超时？
  • 会超时。$10^{10} \times \log N$ 会导致 TLE。此时必须使用二分答案，其复杂度主要取决于值域的对数 $O(N \log(\text{Range}))$，与 $K$ 的具体大小关系较弱（只要 $K$ 足够大能支持 long long 比较即可）。

2. 关于题目二（连续子数组和）的扩展思考

• 如果数组元素可能为负数，还可以使用滑动窗口吗？
  • 不可以。滑动窗口依赖于区间的单调性（即扩张窗口和增加，收缩窗口和减小）。若有负数，单调性破坏，双指针无法确定移动方向。
• 如果数组元素可能为负数，还可以使用二分吗？
  • 不可以。二分查找依赖于前缀和数组的有序性。若有负数，前缀和不再单调递增。
• 如果数组元素可能为负数，还可以使用前缀和+哈希吗？
  • 可以。这是通解，因为它只依赖等式 Pre[i] - Pre[j] = S，不依赖单调性。

---

数组经过K次操作后的最大值

解法一：二分答案（标准解法）

思路：
二分枚举最终可能的最大值 $x$。
check(x) ：计算将数组中所有大于 $x$ 的元素变为 $x$ 所需的操作总数 $ops$。
* 若 $ops \le k$，说明我们可以做到（甚至还能更小），尝试减小 $x$（$r = mid - 1$）。
* 若 $ops > k$，说明次数不够，最大值必然比 $x$ 大，尝试增大 $x$（$l = mid + 1$）。
最终答案即为满足条件的最小 $x$。

#include <bits/stdc++.h>

using ll = long long;
using namespace std;

bool check(ll target, int n, ll k, const vector<ll>& a) {
    ll ops = 0;
    for (ll val : a) {
        if (val > target) {
            ops += (val - target);
        }
        if (ops > k) return false;
    }
    return ops <= k;
}

void solve()
{
    int n;
    ll k;
    cin >> n >> k;
    vector<ll> a(n);
    ll max_val = -2e18; 
    ll min_val = 2e18;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        max_val = max(max_val, a[i]);
        min_val = min(min_val, a[i]);
    }

    // 二分范围：
    // 上界是原数组最大值
    // 下界理论上可以是 min_val - k (建议直接使用-1e10，不需要思考边界且性能折损也很小)
    ll l = min_val - k, r = max_val;
    ll ans = max_val;

    while (l <= r) {
        ll mid = l + (r - l) / 2;
        if (check(mid, n, k, a)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    cout << ans << "\n";
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    cin >> t;

    while (t--)
    {
        solve();
    }
}

解法二：优先队列（暴力模拟）

思路：
使用大根堆，每次取出最大值减 1 后放回，重复 $K$ 次。
注意：此解法仅适用于 $K$ 较小的情况。

#include <bits/stdc++.h>

using ll = long long;
using namespace std;

void solve()
{
    int n;
    ll k;
    cin >> n >> k;
    priority_queue<ll> pq;
    for (int i = 0; i < n; i++) {
        ll x;
        cin >> x;
        pq.push(x);
    }

    while (k--) {
        ll top = pq.top();
        pq.pop();
        pq.push(top - 1);
    }

    cout << pq.top() << "\n";
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    cin >> t;

    while (t--)
    {
        solve();
    }
}

---

连续子数组和计数

解法一：滑动窗口（双指针）

思路：
维护窗口 [l, r] 和窗口和 sum。
由于全是正整数：
* sum < S：右移 r。
* sum > S：右移 l。
* sum == S：记录答案，并继续尝试（通常右移 l 或 r 均可，这里配合循环逻辑处理）。

#include <bits/stdc++.h>

using ll = long long;
using namespace std;

void solve()
{
    int n;
    ll S;
    cin >> n >> S;
    vector<ll> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    ll sum = 0;
    ll count = 0;
    int l = 0;

    for(int r = 0; r < n; r++) {
        sum += a[r];
        while(sum > S && l <= r) {
            sum -= a[l];
            l++;
        }
        if(sum == S) {
            count++;
        }
    }
    cout << count << "\n";
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    // cin >> t;

    while (t--)
    {
        solve();
    }
}

解法二：前缀和 + 二分查找

思路：
因为 $a_i > 0$，前缀和数组 pre 严格单调递增。
对于每个右端点 i，寻找是否存在 pre[j] == pre[i] - S。直接在 pre 数组上使用 binary_search。

#include <bits/stdc++.h>

using ll = long long;
using namespace std;

void solve()
{
    int n;
    ll S;
    cin >> n >> S;

    vector<ll> pre(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        ll x;
        cin >> x;
        pre[i] = pre[i-1] + x;
    }

    ll count = 0;
    for (int i = 1; i <= n; i++) {
        ll target = pre[i] - S;
        // 在 0 到 i-1 的范围内查找 target
        if (binary_search(pre.begin(), pre.begin() + i, target)) {
            count++;
        }
    }
    cout << count << "\n";
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    // cin >> t; 

    while (t--)
    {
        solve();
    }
}

解法三：前缀和 + 哈希表

思路：
最通用的解法。使用 map 记录前缀和出现的次数。
公式：count += mp[current_pre - S]。

#include <bits/stdc++.h>

using ll = long long;
using namespace std;

void solve()
{
    int n;
    ll S;
    cin >> n >> S;

    map<ll, int> mp;
    mp[0] = 1; // 初始化：和为0出现1次

    ll cur = 0;
    ll ans = 0;

    for (int i = 0; i < n; i++) {
        ll x;
        cin >> x;
        cur += x;
        if (mp.count(cur - S)) {
            ans += mp[cur - S];
        }
        mp[cur]++;
    }
    cout << ans << "\n";
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    // cin >> t;

    while (t--)
    {
        solve();
    }
}