P2949 [USACO09OPEN] Work Scheduling G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
反悔贪心
记录详情 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 100010;
int n, m;
PII g[N];
priority_queue<PII, vector<PII>, greater<PII>> q;
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ )
{
int l, r;
scanf("%d%d", &l, &r);
g[i] = {l, r};
}
sort(g + 1, g + 1 + n);
LL ans = 0;
for (int i = 1; i <= n; i ++ )
{
swap(g[i].x, g[i].y);
if (g[i].y > q.size())
{
q.push(g[i]);
ans += g[i].x;
}
else
{
auto t = q.top();
if (t.x >= g[i].x) continue;
q.pop();
q.push(g[i]);
ans -= t.x;
ans += g[i].x;
}
}
cout << ans << endl;
return 0;
}
线段树上二分
记录详情 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 200010;
int n, m;
PII g[N];
int trs[N];
bool st[N];
struct Node
{
int l, r;
int sum;
}tr[N * 4];
void pushup(Node &u, Node &l, Node &r)
{
u = {l.l, r.r, l.sum + r.sum};
}
void pushup(int u)
{
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r)
{
if (l == r) tr[u] = {l, r, 0};
else
{
tr[u] = {l, r};
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int x, int k)
{
if (tr[u].l == tr[u].r) tr[u].sum = k;
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, k);
else modify(u << 1 | 1, x, k);
pushup(u);
}
}
int query(int u, int l, int r)
{
if (tr[u].l == tr[u].r)
{
if (tr[u].sum) return -1;
return tr[u].l;
}
else if (l <= tr[u].l && tr[u].r <= r)
{
int ls = tr[u << 1 | 1].l, rs = tr[u << 1 | 1].r, len = rs - ls + 1;
if (tr[u << 1 | 1].sum < len) return query(u << 1 | 1, l, r);
else return query(u << 1, l, r);
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
int res = -1;
if (r > mid) res = query(u << 1 | 1, l, r);
if (res == -1 && l <= mid) res = query(u << 1, l, r);
return res;
}
}
int query1(int u, int l, int r)
{
if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
else
{
int mid = tr[u].l + tr[u].r >> 1, sum = 0;
if (r > mid) sum += query1(u << 1 | 1, l, r);
if (l <= mid) sum += query1(u << 1, l, r);
return sum;
}
}
int main()
{
cin >> n;
int maxv = 0;
for (int i = 1; i <= n; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
a = min(a, 100010);
g[i] = {b, a};
maxv = max(a, maxv);
}
sort(g + 1, g + 1 + n);
reverse(g + 1, g + 1 + n);
build(1, 1, maxv);
LL sum = 0;
for (int i = 1; i <= n; i ++ )
{
int x = query(1, 1, g[i].y);
// cout << x << endl;
if (x != -1)
{
modify(1, x, 1);
// cout << x << endl;
sum += g[i].x;
}
}
cout << sum << endl;
return 0;
}
树状数组 + 二分
记录详情 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 100010;
int n, m;
PII g[N];
int trs[N];
struct Node
{
int l, r;
int sum;
}tr[N * 4];
bool cmp(PII a, PII b)
{
return a.x > b.x;
}
void pushup(Node &u, Node &l, Node &r)
{
u = {l.l, r.r, l.sum + r.sum};
}
void pushup(int u)
{
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r)
{
if (l == r) tr[u] = {l, r, 0};
else
{
tr[u] = {l, r};
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int x, int k)
{
if (tr[u].l == x && tr[u].r == x) tr[u].sum = k;
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, k);
else modify(u << 1 | 1, x, k);
pushup(u);
}
}
int query(int u, int l, int r)
{
if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
else
{
int mid = tr[u].l + tr[u].r >> 1, sum = 0;
if (l <= mid) sum += query(u << 1, l, r);
if (r > mid) sum += query(u << 1 | 1, l, r);
return sum;
}
}
int find(int x)
{
int l = 0, r = x;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (query(1, max(1, mid), x) < x - mid + 1) l = mid;
else r = mid - 1;
}
return l;
}
int main()
{
cin >> n;
int maxv = 0;
for (int i = 1; i <= n; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
a = min(a, (int)1e5);
g[i] = {b, a};
maxv = max(a, maxv);
}
sort(g + 1, g + 1 + n, cmp);
build(1, 1, maxv);
LL sum = 0;
for (int i = 1; i <= n; i ++ )
{
int x = find(g[i].y);
if (x)
{
modify(1, x, 1);
sum += g[i].x;
}
}
cout << sum << endl;
return 0;
}
标签:Node,USACO09OPEN,PII,int,sum,Work,mid,Scheduling,include
From: https://www.cnblogs.com/blind5883/p/18538634