Diamondz

5.0万

Diamondz
20小时前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 50010;

struct Cow {
int w, s;
bool operator< (const Cow& W)const {
return w + s < W.w + W.s;
}
} cows[N];

int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> cows[i].w >> cows[i].s;
sort(cows, cows + n);

int res = -2e9;
for (int i = 0, s = 0; i < n; i++) {
res = max(res, s - cows[i].s);
s += cows[i].w;
}
cout << res << endl;

return 0;
}


#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int a[N];

int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
sort(a, a + n);

int mid = a[n / 2], res = 0;
for (int i = 0; i < n; i++) res += abs(a[i] - mid);
cout << res << endl;

return 0;
}


#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int a[N];

int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
sort(a, a + n);

long long res = 0, s = 0;
for (int i = 0; i < n - 1; i++) {
s += a[i];
res += s;
}
cout << res << endl;

return 0;
}


#include <iostream>
#include <queue>

using namespace std;

const int N = 10010;

int a[N];

int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];

priority_queue<int, vector<int>, greater<int>> heap;
int res = 0;
for (int i = 0; i < n; i++) heap.push(a[i]);
while (heap.size() > 1) {
int x = heap.top(); heap.pop();
int y = heap.top(); heap.pop();
res += x + y;
heap.push(x + y);
}
cout << res << endl;

return 0;
}


#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

struct Range {
int l, r;
bool operator< (const Range& W)const {
return l < W.l;
}
} range[N];

int main() {
int st, ed;
cin >> st >> ed;
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> range[i].l >> range[i].r;
sort(range, range + n);

int res = 0;
bool flag = false;
for (int i = 0; i < n; i++) {
int j = i, r = -2e9;
while (j < n && range[j].l <= st) {
r = max(r, range[j].r);
j++;
}
if (r < st) {
flag = false;
break;
}
res++;
if (r >= ed) {
flag = true;
break;
}
i = j - 1;
st = r;
}
if (!flag) cout << -1 << endl;
else cout << res << endl;

return 0;
}


#### 按左端点排序

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

struct Range {
int l, r;
bool operator<(const Range& w)const {
return l < w.l;
}
} range[N];

int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> range[i].l >> range[i].r;

sort(range, range + n);
priority_queue<int, vector<int>, greater<int>> heap;
for (int i = 0; i < n; i++) {
if (heap.size() && range[i].l > heap.top()) {
heap.pop();
heap.push(range[i].r);
} else heap.push(range[i].r);
}
cout << heap.size() << endl;

return 0;
}


#### 按右端点排序

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

struct Range {
int l, r;
bool operator<(const Range& w)const {
return r < w.r;
}
} range[N];

int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> range[i].l >> range[i].r;

sort(range, range + n);
priority_queue<int> heap;
for (int i = n - 1; ~i; i--) {
if (heap.size() && range[i].r < heap.top()) {
heap.pop();
heap.push(range[i].l);
} else heap.push(range[i].l);
}
cout << heap.size() << endl;

return 0;
}


#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

struct Range {
int l, r;
bool operator<(const Range& W)const {
return r < W.r;
}
} range[N];

int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> range[i].l >> range[i].r;
sort(range, range + n);

int res = 0, ed = -2e9;
for (int i = 0; i < n; i++) {
if (range[i].l > ed) {
res++;
ed = range[i].r;
}
}
cout << res << endl;

return 0;
}


#### 右端点排序

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

struct Range {
int a, b;
bool operator<(const Range& r) const {
return b < r.b;
}
} ranges[N];

int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> ranges[i].a >> ranges[i].b;
sort(ranges, ranges + n);

int res = 0;
int cur = -2e9;
for (int i = 0; i < n; i++) {
if (ranges[i].a > cur) {
res++;
cur = ranges[i].b;
}
}
cout << res << endl;

return 0;
}


#### 左端点排序

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

struct Range {
int l, r;
bool operator<(const Range& range)const {
return l < range.l;
}
} range[N];

int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> range[i].l >> range[i].r;

sort(range, range + n);
int res = 0, ed = -2e9;
for (int i = 0; i < n; i++) {
if (range[i].l > ed) {
res++;
ed = range[i].r;
} else ed = min(ed, range[i].r);
}
cout << res << endl;

return 0;
}


#include <iostream>
#include <cstring>

using namespace std;

const int N = 310;

int f[N][N], g[N][N];
int n, m;

int dp(int x, int y) {
if (f[x][y] != -1) return f[x][y];
f[x][y] = 1;

int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
for (int i = 0; i < 4; i++) {
int a = x + dx[i], b = y + dy[i];
if (a < 0 || a >= n || b < 0 || b >= m) continue;
if (g[a][b] < g[x][y]) f[x][y] = max(f[x][y], dp(a, b) + 1);
}
return f[x][y];
}

int main() {
cin >> n >> m;

for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> g[i][j];

memset(f, -1, sizeof f);
int res = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
res = max(res, dp(i, j));
cout << res << endl;

return 0;
}


#include <iostream>
#include <cstring>

using namespace std;

const int N = 6010;

int f[N][2];
int e[N], ne[N], h[N], idx;
bool st[N];
int w[N];

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

void dfs(int u) {
f[u][1] = w[u];
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
dfs(j);
f[u][0] += max(f[j][0], f[j][1]);
f[u][1] += f[j][0];
}
}

int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> w[i];

memset(h, -1, sizeof h);
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;