一、文件操作

1. 加头文件

#include <cstdio>

cstdio 表示 C 语言中标准的输入输出。

2. 加函数

int main()
{freopen("输入文件名.in", "r", stdin);freopen("输出文件名.out", "w", stdout);// 这里写代码...fclose(stdin);fclose(stdout);return 0;
}

3. 写输入

在与程序同一目录下创建 name.in 文件，在里面输入要输入的内容，然后运行程序，得到 name.out 文件，就可以看到输出的内容了。

二、贪心算法

1. 概念

贪心算法 greedy algorithm
在对问题求解时，总是做出在当前看来是最好的选择，来期望达到整体最优。

2. 洛谷P2240 最多的金币

2.1 审题

题目描述

阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有 $N(N\le 100)$ 堆金币，第 $i$ 堆金币的总重量和总价值分别是 $m_i,v_i(1\le m_i,v_i\le 100)$ 。阿里巴巴有一个承重量为 $T(T\le 1000)$ 的背包，但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割，分割完的金币重量价值比（也就是单位价格）不变。请问阿里巴巴最多可以拿走多少价值的金币？

输入格式

第一行两个整数 $N,T$ 。
接下来 $N$ 行，每行两个整数 $m_i,v_i$ 。

输出格式

一个实数表示答案，输出两位小数。

样例1

输入

4 50
10 60 
20 100 
30 120 
15 45

输出

240.00 

2.2 解题思路

• 求除 $n$ 堆金币的单位价值，也就是这对金币的价值除以重量。
• 把这 $n$ 堆金币按照单价排序，从高到低遍历。
• 如果背包中剩余的重量大于等于这对金币的重量，就把这对拿走。
• 否则将这对金币分割，把剩余的空间全部装满。

2.3 参考答案

#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;int n, t;
double weight;struct Node
{int m, v;double per;
}a[105];bool cmp(Node a, Node b)
{return a.per > b.per;
}int main()
{cin >> n >> t;for (int i = 1; i <= n; i++){cin >> a[i].m >> a[i].v;a[i].dj = a[i].v * 1.0 / a[i].m; // 计算单价}sort(a+1, a+n+1, cmp); // 排序// 拿金币for (int i = 1; i <= n; i++){if (a[i].m <= t) // 不超载的情况下{weight += a[i].v; // 计算载重t -= a[i].m; // 计算剩余重量}else{weight += a[i].per * t;break;}}cout << fixed << setprecision(2) << w;return 0;
}

3. 洛谷P2240反向

3.1 审题

题目描述

有一批快递要装上一辆载重量为 $c$ 的快递车进行运送。第 $i$ 个快递的重量为 $W_i$ 。由于每件快递都很小，几乎不占快递车的空间，但是都比较重。为了节省成本，因此需要考虑在装载体积不受限制的情况下，将尽可能多的快递装上快递车，请你编程帮助快递小哥求出来最多能装载多少件快递。

输入描述

第一行共两个整数 $N,c$ ，表示快递的件数和快递车的载重量。
第二行共有 $N$ 个整数，分别表示快递的重量 $W_i$ 。

输出描述

共一行，输出 $1$ 个整数，表示最多能装载的快递件数。

样例1

输入

8
400 100 200 50 90 150 50 20 80

输出

6

提示

对于 $100％$ 的数据，$N\le 100$ ，$c\le 10000$ 。

3.2 参考答案

#include <iostream>
#include <algorithm>
using namespace std;int n, c, maxn = 0;
int a[105];int main()
{cin >> n >> c;for (int i = 1; i <= n; i++){cin >> a[i];}sort(a+1, a+n+1);for (int i = 1; i <= n; i++){if (a[i] <= c){c -= a[i];maxn++;}else{break;}}cout << maxn;return 0;
}

4. 贪心的资本家

4.1 审题

题目描述

可多饭店本月新收到若干个不同的菜单，制作这些菜单上的菜的难易程度为一级、二级、三级…同样，能够制作不同难度菜单的厨师也被分为若干星级，并且 $x$ 星级的厨师能够完成 $x$ 级别及以下的所有菜单上的菜，高星级的菜优先由高星级的厨师完成。现有 $m$ 个菜单需要制作，$n$ 个空闲厨师，请问能否完成所有菜单呢？如果可以，最少的花费是多少呢？注：每个厨师当月只能完成一份菜单，厨师的工资就是厨师的星级。

输入描述

输入文件为 capital.in
输入第一行两个整数 m 和 n，分别表示需要制作的菜单量和空闲厨师的人数。
第二行 m 个整数，表示每个菜单的难易级别；
第三行 n 个整数，表示每个厨师的星级。

输出描述

输出文件为 capital.out
如果可以完成：第一行输出最小花费，接下来m行每行两个整数，分别表示菜单级别与相应的厨师级别（用空格隔开）。
否则，直接输出“Failed”

样例1

输入

5 2 
5 4 1 2 3 
7 8

输出

Failed

样例2

输入

5 7 
5 4 6 6 3 
3 5 9 10 6 8 5 

输出

27 
3 3 
4 5 
5 5 
6 6 
6 8

提示

$1\le n,m\le 20000$

4.2 参考答案

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;int n, m, j, money;
int food[20005];
int cook[20005];struct Node
{int f, c;
}f[20005];int main()
{freopen("capital.in", "r", stdin);freopen("capital.out", "w", stdout);cin >> m >> n;if (n < m){cout << "Failed";fclose(stdin);fclose(stdout);return 0;}for (int i = 1; i <= m; i++){cin >> food[i];}for (int i = 1; i <= n; i++){cin >> cook[i];}sort(food+1, food+m+1);sort(cook+1, cook+n+1);j = 1;for (int i = 1; i <= m; i++){while (food[i] > cook[j]){j++;}if (j > n){cout << "Failed";fclose(stdin);fclose(stdout);return 0;}money += cook[j];f[i].f = food[i];f[i].c = cook[j];j++;}cout << money << endl;for (int i = 1; i <= m; i++){cout << f[i].f << " " << f[i].c << endl;}fclose(stdin);fclose(stdout);return 0;
}