E-小苯的水瓶

原题：E-小苯的水瓶

题意：

给定 n 个水瓶，每个水瓶有一些水，这些水瓶可以倒水给其他水瓶，但是转移的总和不能超过 m，可以操作任意次，此外还有 k 的水量可以分配给这些水瓶，最后小红会喝掉水量最少的水瓶里的水，问小红最多可以喝多少水

思路：

如果 小红最多能喝 h 的水，那么 h-1, h-2 .... 比 h 少的水量他肯定可以喝到这么多水，满足单调性，可以二分。

check 函数就是把 < limit 的水瓶需要的水量全部加起来，记为 need，另外把多的加起来记为 res，再加上 k，看 need 与 min(res,m)+k 的大小

//      https://ac.nowcoder.com/acm/contest/103864/E

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9 + 7;

int T, n, m, k;
int a[200005];

bool check(int limit)
{
    int res = 0, need = 0;
    for (int i = 0; i < n; i++)
    {
        if (a[i] < limit)
            need += limit - a[i];
        else
            res += a[i] - limit;
    }
    res = min(res, m);
    return need <= res + k;
}

void solve()
{
    cin >> n >> m >> k;
    int mx = 0;
    for (int i = 0; i < n; i++)
        cin >> a[i], mx = max(mx, a[i]);
    // sort(a,a+n);
    int l = 0, r = mx + k / n + 1, ans;
    while (l <= r)
    {
        int mid = (r - l) / 2 + l;
        if (check(mid))
            l = mid + 1, ans = mid;
        else
            r = mid - 1;
    }
    cout << ans << "\n";
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

D-小苯的ovo

原题：D-小苯的ovo

题意：

给定一个只包含 'o'、'v' 的字符串，最多能进行 K 次以下操作：

• 将 'o' -> 'v' 或者 'v' -> 'o'

问最后子串 "ovo" 的数量（字串之间互相独立）

思路：

dp

dp[ i ][ j ] 表示前 i 个位置，花费 j 次操作的最大数量

//      https://ac.nowcoder.com/acm/contest/103864/D

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9 + 7;

int T, n, m, k;
void solve()
{
    cin >> n >> k;
    string s;
    cin >> s;
    vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
    int ans = 0;
    for (int i = 3; i <= n; i++)
    {
        for (int j = 0; j <= k; j++)
        {
            dp[i][j] = dp[i - 1][j];
            int cnt = 0;
            if (s[i - 1] != 'o')
                cnt++;
            if (s[i - 2] != 'v')
                cnt++;
            if (s[i - 3] != 'o')
                cnt++;
            if (j >= cnt)
                dp[i][j] = max(dp[i - 3][j - cnt] + 1, dp[i][j]);
            // ans = max(ans, dp[i][j]);
        }
    }
    cout << dp[n][k] << "\n";
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

G-小苯的奇怪最短路

原题：G-小苯的奇怪最短路

题意：

定义最短路：从 1 -> n 的边中 最大值 + 最小值，求 1 -> n 的最短路

思路：

最小生成树 + 并查集

最小生成树求连通图的过程中再开一个 min 数组用来存每个集合的最小边，如果 1 和 n 连通了，那么最大值的边就是现在这条边，因为 K 算法求最小生成树就是将边按边权从小到大排好序了，那么答案就是 min[f[1]] + 当前的边的权值

//      https://ac.nowcoder.com/acm/contest/103864/G

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

int t, n, m;
int find(vector<int> &f, int a)
{
    if (a != f[a])
        f[a] = find(f, f[a]);
    return f[a];
}

void Union(vector<int> &f, vector<int> &mi, int a, int b, int w)
{
    int fa = find(f, a);
    int fb = find(f, b);
    f[fb] = fa;
    mi[fa] = min(mi[fa], min(mi[fb], w));
}
void solve()
{
    cin >> n >> m;
    vector<vector<int>> v(m, vector<int>(3));
    vector<int> f(n + 1, 0), mi(n + 1, 1e18);
    for (int i = 0; i <= n; i++)
        f[i] = i;
    for (int i = 0; i < m; i++) // m条边
        cin >> v[i][0] >> v[i][1] >> v[i][2];

    // 按边的权值从小到大排序
    sort(v.begin(), v.end(), [](const vector<int> &v1, const vector<int> &v2)
         { return v1[2] < v2[2]; });
    int ans = 1e18;
    for (int i = 0; i < m; i++)
    {
        Union(f, mi, v[i][0], v[i][1], v[i][2]);
        if (find(f, 1) == find(f, n))
        {
            ans = min(ans, mi[find(f, 1)] + v[i][2]); // 因为边按大小已经排好序了，所以现在的 v[i][2] 就是目前的最大边
        }
    }
    cout << (ans == 1e18 ? -1 : ans) << "\n";
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}