头像

fyygfuy


访客:81

离线:10天前


分享 P4447

fyygfuy
10天前
#include <bits/stdc++.h>
using namespace std;

const int N = 2e6 + 10;

int n, tot;
int a[N], st[N], b[N];
map<int, int> M;

bool check(int len) {
    for (int i = 1; i <= tot; i++) {
        b[i] = st[i] - st[i - 1];
    }
    for (int i = 1; i <= tot; i++) {
        if (st[i] > st[i - 1]) {
            if (i + len - 1 > tot) return false;
            int d = st[i] - st[i - 1];
            b[i] -= d, b[i + len] += d;
        }
    }
    for (int i = 1; i <= tot; i++) {
        b[i] += b[i - 1];
        if (b[i] < 0) return false;
    }
    return true;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n);
    a[0] = 1e9 + 7;
    for (int i = 1; i <= n; i++) {
        if (a[i] != a[i - 1]) {
            tot++;
            if (a[i] - a[i - 1] > 1) tot++;
            M[a[i]] = tot;
        }
        st[M[a[i]]]++;
    }

    int l = 1, r = tot;
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l << endl;

    return 0;
}


活动打卡代码 AcWing 341. 最优贸易

fyygfuy
2个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 100010, M = 500010 * 4;

int n, m;
int ha[N], hs[N], e[M], ne[M], idx;
int w[N], f[N], d[N];
bool st[N];

void add(int h[], int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void spfa(int s, int h[], bool flag) {
    queue<int> q;
    q.push(s);
    d[s] = w[s];
    st[s] = true;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        st[u] = false;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (!flag && d[j] > min(d[u], w[j])) {
                d[j] = min(d[u], w[j]);
                if (!st[j]) {
                    st[j] = true;
                    q.push(j);
                }
            } else if (flag && f[j] < max(f[u], w[j])) {
                f[j] = max(f[u], w[j]);
                if (!st[j]) {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
}

int main() {
    memset(ha, -1, sizeof(ha));
    memset(hs, -1, sizeof(hs));
    memset(d, 0x3f, sizeof(d));
    memset(f, -0x3f, sizeof(f));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &w[i]);
    }
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(ha, a, b), add(hs, b, a);
        if (c == 2) {
            add(ha, b, a), add(hs, a, b);
        }
    }
    spfa(1, ha, 0);
    spfa(n, hs, 1);

    int res = 0;
    for (int i = 1; i <= n; i++) {
        res = max(res, f[i] - d[i]);
    }
    printf("%d\n", res);
    return 0;
}


活动打卡代码 AcWing 340. 通信线路

fyygfuy
2个月前
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
const int N = 1010, M = 2010 * 10010;

int n, m, k;
int h[N * N], e[M], w[M], ne[M], idx;
int dist[N * N];
bool st[N * N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int spfa() {
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    st[1] = true;
    queue<int> q;
    q.push(1);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        st[u] = false;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > max(dist[u], w[i])) {
                dist[j] = max(dist[u], w[i]);
                if (!st[j]) {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
    if (dist[n + k * N] == 0x3f3f3f3f) {
        return -1;
    } else {
        return dist[n + k * N];
    }
}

int main() {
    memset(h, -1, sizeof(h));
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
        for (int i = 1; i <= k; i++) {
            add(a + i * N, b + i * N, c);
            add(b + i * N, a + i * N, c);
            add(a + (i - 1) * N, b + i * N, 0);
            add(b + (i - 1) * N, a + i * N, 0);
        }
    }

    printf("%d", spfa());

    return 0;
}