fyygfuy

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;
}


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);
if (c == 2) {
}
}
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;
}


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);