贪心

独木舟 原题链接：https://oj.haizeix.com/problem/503 一群人去旅行要租用独木舟，每艘独木舟最多乘两人，且所有独木舟有一个统一的载重限度。 给出独木舟的载重限度和每个人的体重，现求最少需要租用多少独木舟。 输入 第一行一个整数 w，表示独木舟的载重量。（80 ≤ w ≤ 200） 第二行一个整数 n，表示旅游人数。 （1 ≤ n ≤ 30000） 接下来 n 行，每行一个数表示 ai，即每个人的重量 （5 ≤ ai ≤ w） 输出 接下来 n 行，每行一个数表示 ai，即每个人的重量 （5 ≤ ai ≤ w） 样例： 12345678910111009902020305060708090 16 参考代码123456789101112131415161718192021222324252627282930313233#include<iostream>#include<algorithm>using namespace std;int weight[30005];int main() { //1.数据录入 int w;//独木舟载重量 int n;//旅游的人数 cin >> w >> n; for (int i = 0; i < n; ++i) cin >> weight[i]; sort(weight, weight + n); //2.进行数据处理 int count = 0; if (weight[0] * 2 > w) {//特殊情况处理 count = n; } else {//一般情况处理 for (int i = 0; i < n; ++i) { for (int j = n - 1; j >= 0; --j) { if (weight[j] == 0) continue; if ((weight[i] + weight[j]) <= w || i == j) { count++; weight[j] = 0; weight[i] = 0; break; } } } ...

删数 原题链接：https://oj.haizeix.com/problem/504 输入一个高精度的正整数 n（长度不大于 240 位）， 去掉其中任意 s 个数字后，剩下的数字按原左右次序将组成一个新的正整数，现求一种方案，使得新的正整数数值最小。 输入 第一行一个整数 n 第二行一个正整数 s 输出 输出一个数表示最小值，输出时忽略数字的前导零 样例： 123//样例11795664 115 123//样例29030713 11 参考代码 让小的数字在前面、大的数字在后面，使得整体的数字变小。 删除违反该规则的数字， 如果没有违反规则的数字，则删除最后一个数字（最大的数字） 12345678910111213141516171819202122232425262728293031323334#include<iostream>#include<string>using namespace std;int main() { string str; cin >> str; int n; cin >> n; //1.数据操作 for (int i = 0; i < n; ++i) { int ind = str.size() - 1;//默认删除最后一位-1 for (int j = 1; j < str.size(); ++j) { if (str[j - 1] > str[j]) {//优先删除违反规则的数字 ind = j - 1; break; } } str.replace(ind, 1, ""); } //2.前置零的特殊处理 int flag = 0; for (int i = 0; i < str.size(); ++i) { if (flag == 1) { cout << str[i]; } else if (str[i] != '0') { cout << str[i ...

最大整数 原题链接：https://oj.haizeix.com/problem/505 现在有 n 个正整数，将他们连成一排，组成一个最大的整数。 例如，现在有三个整数 13, 312, 343，连接成最大整数为 34331213。 输入： 第一行一个整数 n。（1 ≤ n ≤ 100000） 第二行 n 个不超过 int 类型范围的正整数。 输出： 输出一个数表示组成的最大整数。 样例： 123121 12 96 19612121 参考代码思路：按照某种规则进行排序（前面的字符串 连接上 后面的字符串的字典序，大于后面的字符串连接上前面的字符串的字典序） 123456789101112131415161718192021#include<iostream>#include<algorithm>#include<string>using namespace std;int n;string str[100005];bool cmp(const string &str1, const string &str2) { //前面连接上后面的字典序 大于 后面连接上前面的字典序 return str1 + str2 > str2 + str1;}int main() { cin >> n; for (int i = 0; i < n; ++i) cin >> str[i]; sort(str, str + n, cmp); for (int i = 0; i < n; ++i) cout << str[i]; cout << endl; return 0;}

打热水 原题链接：https://oj.haizeix.com/problem/506 寝室楼里只有热水间能接热水，且每天烧水机器只在指定时间工作，去晚了机器就关掉了，每天晚上去接热水的同学能排起小长队。 某天在总计四个烧水机中，坏了三个只剩下一台机器能打水了。 现在有 n 名同学等待接水，因为每名同学所带的水壶有大有小，规格各不相同所以他们每人的接水时间分别为 Ti， 现求一个顺序，使得所有接水的同学平均等待接水时间最小，等待接水时间为该同学之前接水的同学所花费时间和。 输入 第一行一个整数 n。（1 ≤ n ≤ 30） 第二行 n 个整数表示 Ti。（1 ≤ Ti ≤ 2000） 输出 第一行输出排队顺序 第二行输出平均等待时间，结果保留两位小数。 样例： 121056 12 1 99 1000 234 33 55 99 812 123 2 7 8 1 4 9 6 10 5291.90 参考代码1234567891011121314151617181920212223242526272829303132333435363738#include<iostream>#include<algorithm>#include<cstdio>using namespace std;struct node { int cnt;//打水同学的编号 int time;//所需的打水时间};node stu[35];int n;//同学的数量bool cmp(const node &a, const node &b) { return a.time < b.time;}int main() { //1.数据存储 cin >> n; for (int i = 1; i <= n; ++i) { cin >> stu[i].time; stu[i].cnt = i; } //2.数据处理 sort(stu + 1, stu + n + 1, cmp); int sum = 0;//总打水时间 int now = 0;//某个同学的打水等待时间 for (int i = 1; i <= n; ++i)  ...

两人过河 原题链接：https://oj.haizeix.com/problem/508 有 n 个人希望在晚上通过一座桥。 在任何时刻，最多只能有两个人在桥上，并且必须要带着手电筒才能过桥。 现在只有一个手电筒，所以必须安排某种顺序，使得手电筒可以被带回去让更多的人过桥。 每个人都有不同的过桥时间，两个人一起过桥所用的时间等于其中较慢的一个人的过桥时间。 现求所有人过桥的最短时间。 输入 第一行一个整数 n。（1 ≤ n ≤ 1000） 接下来 n 行，每行一个整数表示第 i 人的过桥时间 Ti。（1 ≤ Ti ≤ 100） 输出 输出所有人过桥的最短时间。 样例： 12345415210 117 让 1, 2 先过桥，然后让 1 回来，让 5,10 过桥，然后 2 回来再和 1 一起过桥，时间为 2+1+10+2+2=17。 思路==思路==：让时间短的人优先过桥，作为工具人。 递归解决问题 有时使用1个人当工具人过桥时间较短，有时使用2个人当工具人过桥时间较短 取两种方案中速度较快的一种（将两种方案结合起来） 参考代码设最快的过桥时间为num[0]、次快过桥时间为num[1]、次慢过桥时间为num[i - 1]、最慢过桥时间为num[i]： 则有： n = 1时，最快过桥时间为num[0] n = 2时，最快过桥时间为num[1] n = 3时，最快过桥时间为num[1] + num[0] + num[2] n > 3时，最快过桥时间为 方案1（2个工具人）：num[1] + num[0] + num[i] + num[1]（此时两个工具人都在起点） 方案2（1个工具人）：num[i] + num[0] + num[i - 1] + num[0]（此时工具人在起点） 1234567891011121314151617181920212223242526272829#include<iostream>#include<algorithm>using namespace std;int n, num[1005];int ans;int main() { cin >> n; for (int i = 0; i & ...

智力大冲浪 原题链接：https://oj.haizeix.com/problem/509 小伟报名参加中央电视台的智力大冲浪节目。 本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气先奖励每个参赛者 m 元，接下来主持人宣布了比赛规则： 首先，比赛时间分为 n 个时段 (n ≤ 500)，它又给出了很多小游戏，每个小游戏都必须在规定期限 ti 前完成 (1 ≤ ti ≤ n )。 如果一个游戏没能在规定期限前完成，则要从奖励费 m 元中扣去一部分钱 wi，不同的游戏扣去的钱是不一样的。 当然，每个游戏本身都很简单保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者，小伟很想赢得冠军当然更想赢取最多的钱。 输入： 第一行为 m，表示一开始奖励给每位参赛者的钱 第二行为 n，表示有 n 个小游戏 第三行有 n 个数，分别表示游戏 1 到 n 的规定完成期限 第四行有 n 个数，分别表示游戏 1 到 n 不能在规定期限前完成的扣款数 输出： 输出小伟能赢取最多的钱 样例： 12341000074 2 4 3 1 4 670 60 50 40 30 20 10 19950 思路 优先完成扣钱多的任务 对于每个可以完成的任务，尽量靠后完成 参考代码1