洛谷【算法1-5】贪心P2240 【深基12.例1】部分背包问题P1223 排队接水P1803 凌乱的yyy / 线段覆盖P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair GP3817 小A的糖果P1106 删数问题P1478 陶陶摘苹果（升级版）P5019 [NOIP2018 提高组] 铺设道路P1208 [USACO1.3]混合牛奶 Mixing MilkP1094 [NOIP2007 普及组] 纪念品分组P4995 跳跳！P4447

74 阅读 0 评论 49 点赞

我是靠谱客的博主勤恳汽车，最近开发中收集的这篇文章主要介绍洛谷【算法1-5】贪心P2240 【深基12.例1】部分背包问题P1223 排队接水P1803 凌乱的yyy / 线段覆盖P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair GP3817 小A的糖果P1106 删数问题P1478 陶陶摘苹果（升级版）P5019 [NOIP2018 提高组] 铺设道路P1208 [USACO1.3]混合牛奶 Mixing MilkP1094 [NOIP2007 普及组] 纪念品分组P4995 跳跳！P4447，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

P2240 【深基12.例1】部分背包问题

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
struct Node {
int w, v;
}a[N];
int read() {
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
x = x * 10 + (c - '0');
c = getchar();
}
return x * f;
}
bool cmp(Node a, Node b) {
// 为防止精度问题直接交叉相承
return a.v * b.w > a.w * b.v;
}
int main() {
int n, t;
n = read(), t = read();
for (int i = 0; i < n; ++ i) {
a[i].w = read(), a[i].v = read();
}
sort(a, a + n, cmp);
double ans = 0;
for (int i = 0; i < n; ++ i) {
if (t >= a[i].w) {
t -= a[i].w;
ans += a[i].v;
} else {
ans += t * 1.0 * a[i].v / a[i].w;
break;
}
}
printf("%.2lf", ans);
}

P1223 排队接水

注意精读，sum不能是int否则会wa几个点（就算*1.0也没用）

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
struct Node {
int time, idx;
}a[N];
bool cmp(Node u, Node v) {
return u.time < v.time;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; ++ i) {
cin >> a[i].time;
a[i].idx = i;
}
sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; ++ i) {
cout << a[i].idx;
if (i != n) cout << ' ';
}
double sum = 0;
for (int i = 1; i <= n - 1; ++ i) {
sum += a[i].time * (n - i);
}
cout << endl;
printf("%.2lf", sum / n);
}

P1803 凌乱的yyy / 线段覆盖

结束越早越好

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
struct Node {
int st, ed;
}a[N];
bool cmp(Node x, Node y) {
return x.ed < y.ed;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; ++ i) {
cin >> a[i].st >> a[i].ed;
}
sort(a + 1, a + n + 1, cmp);
int cnt = 0;
int last = -10;
for (int i = 1; i <= n; ++ i) {
if (last <= a[i].st) {
cnt ++ ;
last = a[i].ed;
}
}
cout << cnt;
}

P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G

剩下最后一堆是答案

#include <iostream>
#include <queue>
using namespace std;
int main() {
priority_queue<int, vector<int>, greater<int>> que;
int n;
cin >> n;
for (int i = 0; i < n; ++ i) {
int x;
cin >> x;
que.push(x);
}
int ans = 0;
while (que.size() > 1) {
int a = que.top(); que.pop();
int b = que.top(); que.pop();
ans += a + b;
que.push(a + b);
}
cout << ans;
}

P3817 小A的糖果

模拟；
贪心过程：每次吃的是两颗中的第二颗（第一颗是模拟必不可少，需特判

#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll a[N];
int main() {
int n;
ll x;
cin >> n >> x;
ll ans = 0;
cin >> a[1];
if (a[1] > x) {
ans += a[1] - x;
a[1] = x;
}
for (int i = 2; i <= n; ++ i) {
cin >> a[i];
if (a[i] + a[i - 1] > x) {
ans += a[i] + a[i - 1] - x;
a[i] = x - a[i - 1];
}
}
cout << ans;
}

P1106 删数问题

外层k轮（因为我们知道k个机会肯定要用完），每次删数要么是遇上的第一个比下一个大的或者是最后一位
string.erase(idx, len)

#include <iostream>
using namespace std;
int main() {
string s;
int k;
cin >> s >> k;
while (k -- ) {
int n = (int)s.size();
for (int i = 0; i < n; ++ i) {
if (i == n - 1 || s[i] > s[i + 1]) {
s.erase(i, 1);
break;
}
}
}
while (s.size() > 1 && s[0] == '0') {
s.erase(0, 1);
}
cout << s;
}

P1478 陶陶摘苹果（升级版）

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5e3 + 10;
struct Node {
int h, w;
}a[N];
bool cmp(Node u, Node v) {
return u.w < v.w;
}
int main() {
int n, s, u, v;
cin >> n >> s >> u >> v;
for (int i = 0; i < n; ++ i) {
cin >> a[i].h >> a[i].w;
}
sort(a, a + n, cmp);
int ans = 0;
for (int i = 0; i < n; ++ i) {
if (a[i].h > u + v) continue;
if (s >= a[i].w) {
ans ++ ;
s -= a[i].w;
} else {
break;
}
}
cout << ans;
}

P5019 [NOIP2018 提高组] 铺设道路

草稿纸上模拟发现，每次是先把从最左边开始的一段给填完，后面的可以看成最左边

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++ i) {
cin >> a[i];
}
int ans = a[0];
for (int i = 1; i < n; ++ i) {
if (a[i] > a[i - 1]) {
ans += a[i] - a[i - 1];
}
}
cout << ans;
}

P1208 [USACO1.3]混合牛奶 Mixing Milk

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5010;
struct Node {
int price, num;
}a[N];
bool cmp(Node u, Node v) {
return u.price < v.price;
}
int main() {
int n, m;
cin >> m >> n;
for (int i = 0; i < n; ++ i) {
cin >> a[i].price >> a[i].num;
}
sort(a, a + n, cmp);
int sum = 0;
for (int i = 0; i < n; ++ i) {
if (a[i].num <= m) {
sum += a[i].price * a[i].num;
m -= a[i].num;
} else {
sum += a[i].price * m;
break;
}
}
cout << sum;
}

P1094 [NOIP2007 普及组] 纪念品分组

双指针
如果只剩下最后一个，一组然后退出循环；如果两个相加可以一组，一组然后左右指针移动；如果两个相加不能一组，意味着大的那个必然只能自己一组，仅右指针移动

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 3e4 + 10;
int a[N];
int main() {
int n, m;
cin >> m >> n;
for (int i = 0; i < n; ++ i)
cin >> a[i];
sort(a, a + n);
int ans = 0;
for (int l = 0, r = n - 1; l <= r; ) {
if (l == r) {
ans ++ ;
break;
} else if (a[l] + a[r] <= m) {
l ++ , r -- ;
ans ++ ;
} else {
r -- ;
ans ++ ;
}
}
cout << ans;
}

P4995 跳跳！

仍然是双指针

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 310;
int h[N];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++ i)
cin >> h[i];
sort(h, h + n);
int l = 0, r = n - 1;
ll ans = 0;
bool ok = true;
int last = 0;
while (l <= r) {
if (ok) {
ok = false;
ans += (h[r] - last) * (h[r] - last);
last = h[r];
r -- ;
} else {
ok = true;
ans += (h[l] - last) * (h[l] - last);
last = h[l];
l ++ ;
}
}
cout << ans;
}

P4447 [AHOI2018初中组]分组

维护一个每个现有的队伍下一个需要的值的数组；
从小往大遍历；每次插入一个新的值，如果有可以插入的队伍，找最后一个队伍（因为从小往大遍历，越后面的队伍开头的值越大，需要相同的值，说明越后面的队伍越短）；如果没有，就新建一个队伍
不使用vector，因此另外开一个数组siz来记录每一个队伍的长度
最小值最大，不一定是二分，可能是贪心

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N], q[N];
int length;
int siz[N];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++ i)
cin >> a[i];
sort(a, a + n);
for (int i = 0; i < n; ++ i) {
int pos = lower_bound(q, q + length, a[i]) - q;
while (pos + 1 < length && q[pos + 1] == a[i]) pos ++ ;
if (pos >= length || q[pos] != a[i]) {
q[length] = a[i] + 1;
siz[length ++ ] = 1;
} else {
q[pos] = a[i] + 1;
siz[pos] ++ ;
}
}
int mi = 1e9;
for (int i = 0; i < length; ++ i)
mi = min(mi, siz[i]);
cout << mi;
}

P1080 [NOIP2012 提高组] 国王游戏

高精度乘法：首先每一位都乘上x，再从最低位开始进位；注意tmp需要的是while不是if
高精度除法：结果数组长度首先设为被除数的长度，然后清空结果数组内容；从被除数的最高位开始除以x；最后用while清除前导零
高精度比较大小：首先如果长度大肯定大；如果长度相等，从最高位开始比较

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
struct Node {
ll l, r;
bool operator < (const Node &w) const {
return l * r < w.l * w.r;
}
}coin[N];
int lens = 1, lenm = 1, lena = 1;
int sum[N] = {0, 1}, maxn[N] = {0, 1}, ans[N];
void multi(ll x) {
for (int i = 1; i <= lens; ++ i)
sum[i] *= x;
int tmp = 0;
for (int i = 1; i <= lens; ++ i) {
tmp += sum[i];
sum[i] = tmp % 10;
tmp /= 10;
}
//
if (tmp) {
//
sum[ ++ lens] = tmp;
//
}
while (tmp) {
sum[ ++ lens] = tmp % 10;
tmp /= 10;
}
}
void div(ll x) {
lena = lens;
memset(ans, 0, sizeof ans);
int tmp = 0;
for (int i = lena; i >= 1; -- i) {
tmp = tmp * 10 + sum[i];
if (tmp >= x) {
ans[i] = tmp / x;
tmp %= x;
}
}
while (lena > 1 && ans[lena] == 0) {
lena -- ;
}
}
void check_max() {
if (lenm < lena) {
for (int i = 1; i <= lena; ++ i)
maxn[i] = ans[i];
lenm = lena;
} else if (lenm == lena) {
for (int i = lena; i >= 1; -- i) {
if (maxn[i] < ans[i]) {
for (int j = 1; j <= lena; ++ j)
maxn[j] = ans[j];
break;
}
}
}
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n + 1; ++ i)
cin >> coin[i].l >> coin[i].r;
sort(coin + 1, coin + n + 1);
for (int i = 1; i <= n; ++ i) {
multi(coin[i - 1].l);
div(coin[i].r);
check_max();
}
for (int i = lenm; i >= 1; -- i)
cout << maxn[i];
}