目录

🌼一，1812: [NewOJ Week 5] 排列变换

🌼二，1827: [NewOJ Week 8] 升降数字

🌼三，剑指offer 10-II 青蛙跳台阶问题

🌼四，P1223 排队接水

🌼五，P5650 基础字符串练习题

🌼六， 1143: 挤牛奶

🌼七， 1148: 混合牛奶

🌼八，2035: [蓝桥杯2022初赛] X进制减法

🌼九， 1125: 打地鼠                  未完成

🌼十， 1161: 三值排序

🌼十一，P1614 爱与愁的心痛

🌼十二，P2240 【深基12.例1】部分背包问题

题目，解析，代码，输入输出以及题目来源一一列出，需要的同学还可到题目来源自己试试，看能否Accepted，题目难度不分先后

复习时请点击题目来源，自己做一遍，不会的可以在评论区讨论

困难：一，五，六，八，九，十，十二（第一次35min内搞不定）

简单：二，三，四，七，十一

贪心算法一般适用于，需要高效占用某一公共资源的活动，比如

 它实际上不是真正的算法，而是一种思路，这就需要我们在草稿纸上列出清楚的思路，

通过局部最优解推出全局最优解，不确定能否借局部得到全局时，可用反证法

如果举出反例，则不能仅使用贪心，而要靠动态规划等其他算法

贪心算法比较基础的有3个类型，分数背包，数字拼接，活动选择

🌼一，1812: [NewOJ Week 5] 排列变换

题目

给定一个长度为n的排列a，需要将这个排列变成b
每次可以选择一个数字往左移若干个位置
请求出最小移动次数

输入格式

第一行为正整数n，1≤n≤100000
第二行为n个整数，表示排列a
第三行为n个整数，表示排列b

输出格式

输出一个数字表示答案

输入

5
5 1 3 2 4
4 5 2 1 3

输出

2

类型：思维题，贪心 ，基础题

解析

1，

首先，我们需要两个数组保存两个排列

然后通过数组 seat[] 将b[i]中元素与下标对应起来，即seat[b[i]] = i

接着数组a中元素作为seat[]下标，得到a[i] 在 b 中下标，存到数组c[]中，即 c[i] = seat[a[i]] 也就是得到了原排列的元素在b排列中的位置

比如 a = {9, 4, 7, 8, 6, 1}, b = {7, 8, 1, 4, 9, 6}, seat = {3, 0, 0, 4, 0, 6, 1, 2, 5}

最后c = {5, 4, 1, 2, 6, 3}，看草稿

关键：原题目通过seat[]数组和c[]数组，转化为，求通过几次左移，使 5, 4, 1, 2, 6, 3 变成 1, 2, 3, 4, 5, 6
如果直接两次for循环，从5开始，看4，1，2，6，3有无比5小的，再从4开始，看1，2，6，3有无比4小的，再。。。时间会超限，所以

2，

我们采取类似逆序数的思路，比如3，2，5，1，4中，3左边比它大的数没有，2有，5没有，1有，4有，共3个有，所以需要移动3次 

3，

注意！代码第21行 seat[b[i]] = i 和第25行 c[i] = seat[a[i]]要分别放在两个for循环中，否则seat[]数组数据未输入完，c[i] = ....会出现等于0的情况，造成输出错误

代码1

#include
#include //memset()
#include //max()
using namespace std;int a[100010], b[100010];
int c[100010], seat[100010];
//数组seat保存数组b元素对应的下标
//数组c保存数组a元素在b中的下标int main()
{memset(a, 0, sizeof(a)); //初始化数组memset(b, 0, sizeof(b));int n;cin>>n;for(int i = 1; i <= n; ++i) //下标从1开始cin>>a[i];for(int i = 1; i <= n; ++i) {cin>>b[i];seat[b[i]] = i; //b[i]为元素, i为下标}for(int i = 1; i <= n; ++i) {c[i] = seat[a[i]]; //seat[a[i]]为a中元素在b的下标} //由此转化为求数组c变成正序的需要移动的次数int ans = 0; //记录左移最小次数int Max = 0; //保留当前最大值for(int i = 1; i <= n; ++i) {if(c[i] < Max) ans++;Max = max(Max, c[i]);}cout<

6
9 4 7 8 6 1
7 8 1 4 9 6
45
5 1 3 2 4
4 5 2 1 3
29
19 16 13 22 37 12 11 10 -5
-5 10 11 19 16 13 12 37 22
5

5
29041
56577
12345
54300
135341

29000
56555
12345
54300
135333

#include
#include //memset()
using namespace std;int a[100010];int main()
{memset(a, 0, sizeof(a)); //初始化数组全部元素为0int n;cin>>n; //n组测试数据while(n) {string s; //将正整数按字符串输入cin>>s;for(int i= 0; i < s.size(); ++i)a[i] = s[s.size() - 1 - i] - '0'; //从字符串最后一位开始存入数组首位//bug1: 我第一次漏了- '0'，字符串转ASCII常漏，比如转小写字母需要- 'a'int seat = 0, flag = 0; //保存上升前最后一个下降的位置for(int i = s.size() - 1; i >= 0; --i) { //逆序，即从大到小开始比较if(a[i - 1] < a[i]) {seat = i - 1;flag = 1;}if(flag == 1 && a[i - 1] > a[i]) //出现下降后又上升break;}for(int i = seat; i >= 0; --i)a[i] = a[seat]; //上升后又下降的最后一个元素，之后的都一样for(int i = s.size() - 1; i >= 0; --i) //逆序输出cout<

8
29041
29000
56577
56555
12345
12345
54300
54300
135341
135333
99878
99877
132100
132100
531201
531111

#include
#include //memset()
using namespace std;int main()
{int a[110];memset(a, 0, sizeof(a));int n;cin>>n;a[0] = 1;a[1] = 1;a[2] = 2;for(int i = 3; i <= n; ++i) {a[i] = (a[i - 1] + a[i - 2]) % 1000000007;}cout<

class Solution {
public:int numWays(int n) {int a[110];memset(a, 0, sizeof(a));a[0] = 1;a[1] = 1;a[2] = 2;//cin>>n; 就这个cin害我搞了3小时答案错误for(int i = 3; i <= n; ++i) {a[i] = (a[i - 1] + a[i - 2]) % 1000000007;}return a[n];}
};

7
2110
8945
836311896100
782204094

10 
56 12 1 99 1000 234 33 55 99 812

3 2 7 8 1 4 9 6 10 5
291.90

#include
#include //sort()
#include //setprecision(), setiosflags(ios::fixed)
using namespace std;struct people //结构体可以将多个数据对应起来
{int time, num;
};bool cmp(people x, people y)
{return x.time < y.time;
}//sort对结构体排序最好声明个比较函数int main()
{int n;cin>>n;struct people a[1010];for(int i = 1; i <= n; ++i) {cin>>a[i].time; //保存时间a[i].num = i; //保存下标}sort(a + 1, a + 1 + n, cmp); //a的话起始地址默认a[0],而我们从下标1开始,所以a + 1for(int i = 1; i <= n; ++i) cout<

12
8147 12 34 483942 111 99999 12 259 325 1 0 1024
11 10 2 7 3 5 8 9 12 1 6 4
10256.50

0111100101

2

#include
using namespace std;int a[100010]; //|S|表示字符串S的长度
int b[100010]; //保存sum可能的最大值int main()
{string s;cin>>s;for(int i = 0; i < s.size(); ++i)a[i] = s[i] - '0'; //字符转整型存入数组int sum = 0;int zero = 0, one = 0; //保存连续出现的0和1int flag = 0; //做标记，判断先遇到连续0int m = 0; //数组b下标，数组b用以保存可能的sum//核心代码↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓for(int i = 0; i < s.size(); ++i) {if(a[i] == 0) { //遇到0one = 0;zero += 1;flag = 1;}if(a[i] == 1 && flag == 1) {//连续0后遇到1one += 1;b[m++] += zero; //先把当前连续0保存起来}if(one != 0 && flag == 1 && a[i + 1] == 0) { //连续0连续1再遇到0之前flag = 0;if(zero - one > 0)sum += (zero - one);if(zero - one < 0) {b[m++] = sum;sum = 0; //如果出现类似00111情况，继续连续sum会变小，所以断掉}}if(one >= 1 && a[i + 1] == 0) {zero = 0;one = 0;}}for(int i = 0; i < sizeof(b) / sizeof(b[0]); ++i) //这样求整型型数组长度sum = max(sum, b[i]);//分类讨论补充个坑点：当全是1，由于字符串非空，此时应该输出-1if(sum == 0) cout<<-1<

#include
using namespace std;int a[100010];int main()
{string s;cin>>s;for(int i = 0; i < s.size(); ++i)a[i] = s[i] - '0';int sum = -1, zero = 0; //sum初始化-1, 如果出现全是1的情况，输出-1for(int i = 0; i < s.size(); ++i) {if(a[i] == 0) zero++;  //遇0加1else zero--;           //遇1减1if(zero < 0) zero = 0; //不满足最大值就重新计算if(zero > sum) sum = zero; //每一步都进行一次最大值判断}if(sum == 0) cout<<-1<

1110010000010110010100010100101
9111111111111111111111111111111111111
-10111100101
21111111000110100100010000000001111100
1311111111111111111111011111111111111111111111111111111111111111111111
1

3
300 1000
700 1200
1500 2100

900 300

#include
#include //sort()
using namespace std;
struct cow
{int fir, en;
};
bool cmp(cow x, cow y)
{return x.en < y.en;
}int main()
{struct cow a[5010];int n;cin>>n;for(int i = 0; i < n; ++i)cin>>a[i].fir>>a[i].en;sort(a, a + n, cmp); //按结束时间从小到大排序int yes = 0, no = 0;//yes当前挤奶最大值,no当前无人最大值int Max = 0, Min = 1000000; //Min先取最大值，Max先取最小值for(int i = 0; i < n; ++i) {Min = min(Min, a[i].fir);if(a[i].en >= a[i + 1].fir) { //如果能连续Min = min(Min, a[i + 1].fir); //保留连续段中最早的时间Max = max(Max, a[i + 1].en); //保留最晚时间yes = max(yes, Max - Min);}else {       //如果不连续了Max = 0;Min = 1000000; //这样取值便于后续更新数据no = max(no, a[i + 1].fir - a[i].en);}}cout<

#include
#include //sort()
using namespace std;struct cow
{int fir, en;
};bool cmp(cow x, cow y)
{if(x.fir != y.fir)return x.fir < y.fir;
}int main()
{struct cow a[5010];int n;cin>>n;for(int i = 0; i < n; ++i)cin>>a[i].fir>>a[i].en;sort(a, a + n, cmp); //按开始时间从小到大对结构体排序int Max = 0, Min = 1000000, yes = 0, no = 0;Max = a[0].en, Min = a[0].fir; //要点4, 开始设个初始，不要在for里再设for(int i = 1; i < n; ++i) {if(Max >= a[i].fir) { //要点1,这里是Max >=Max = max(Max, a[i].en);Min = min(Min, a[i].fir);}else {yes = max(yes, Max - Min);no = max(no, a[i].fir - Max); //要点2,这里是 - MaxMax = a[i].en;Min = a[i].fir; //要点3,重新开始}}yes = max(yes, Max - Min); //要点5, 防止突然杀出个程咬金，最后最长cout<

3
300 1000
700 1200
1500 2100
900 3008
200 1200
100 500
400 1000
1700 3100
1400 2800
1500 2000
3900 4200
6000 6100
1700 18004
200 800
800 1200
100 1500
1300 2400
2300 0

100 5
5 20
9 40
3 10
8 80
6 30

630

#include
#include //sort()
using namespace std;struct man
{int price, num;
};bool cmp(man x, man y)
{return x.price < y.price;
}int main()
{struct man a[5010];int n, m;cin>>n>>m; //m为奶农数量，n为需要的牛奶数量for(int i = 0; i < m; ++i)cin>>a[i].price>>a[i].num;sort(a, a + m, cmp);int sum = 0, ans = 0; //sum已有的牛奶数量，ans为最小花费for(int i = 0; i < m; ++i) {if(sum + a[i].num <= n) {sum += a[i].num;ans += a[i].num * a[i].price;}else {ans += (n - sum) * a[i].price;break; //不要漏}}cout<

100 5
5 20
9 40
3 10
8 80
6 30
630

11
3
10 4 0
3
1 2 0

94

#include
using namespace std;
const int mod = 1000000007;
int a[100010], b[100010];
int main()
{int N, ma, mb;cin>>N; //感觉N没什么卵用cin>>ma; for(int i = ma - 1; i >= 0; --i) cin>>a[i];//反着存，便于后续遍历cin>>mb; for(int i = mb - 1; i >= 0; --i) cin>>b[i];long long ans = 0, pro = 1, aaa = 0, bbb = 0; //pro(duct)所有前面的乘积for(int i = 0; i < ma; ++i) { //从最小位数开始aaa = (aaa + a[i] * pro) % mod;bbb = (bbb + b[i] * pro) % mod;pro = (pro * max(max(a[i], b[i]) + 1, 2)) % mod;ans = (aaa - bbb) % mod;}cout<

#include
using namespace std;
const int mod = 1000000007;
int a[100010], b[100010];
int main()
{int N, ma, mb;cin>>N; //感觉N没什么卵用cin>>ma; for(int i = ma - 1; i >= 0; --i) cin>>a[i];//反着存，便于后续遍历cin>>mb; for(int i = mb - 1; i >= 0; --i) cin>>b[i];long long ans = 0, pro = 1; //pro(duct)所有前面的乘积for(int i = 0; i < ma; ++i) { //从最小位数开始ans += ((a[i] - b[i]) * pro) % mod;pro = (pro * max(max(a[i], b[i]) + 1, 2)) % mod;}cout<

#include
using namespace std;
const int mod = 1000000007;
int a[100010], b[100010];
int main()
{int N, ma, mb;cin>>N; //感觉N没什么卵用cin>>ma; for(int i = ma - 1; i >= 0; --i) cin>>a[i];//反着存，便于后续遍历cin>>mb; for(int i = mb - 1; i >= 0; --i) cin>>b[i];long long ans = 0, pro = 1; //pro(duct)所有前面的乘积for(int i = 0; i < ma; ++i) { //从最小位数开始ans += ((a[i] - b[i]) * pro);ans %= mod;pro = (pro * max(max(a[i], b[i]) + 1, 2));pro %= mod;}cout<

5
5 3 6 1 4
7 9 2 1 5

24

#include
#include //sort()
using namespace std;
struct mice
{int time, grade;
};
bool cmp(mice x, mice y)
{if(x.time == y.time)return x.grade > y.grade;elsereturn x.time < y.time; //同时对时间和分数排序
}
int main()
{struct mice a[100010];int n, sum = 0, t = 1;cin>>n;for(int i = 1; i <= n; ++i) cin>>a[i].time;for(int i = 1; i <= n; ++i) cin>>a[i].grade;sort(a + 1, a + n + 1, cmp);for(int i = 1; i <= n; ++i)if(a[i].time >= t) { //如果这个地鼠时间没结束sum += a[i].grade;t++;}cout<

9
2
2
1
3
3
3
2
3
1

4

#include
#include //sort()
using namespace std;
int a[1010];
int b[1010];int main()
{int n;cin>>n;for(int i = 0; i < n; ++i) {cin>>a[i];b[i] = a[i];}sort(a, a + n); //a[i]是排序后的，b[i]原排列int one = 0, two = 0, repeat = 0;for(int i = 0; i < n; ++i) {if(a[i] == 1 && b[i] != 1)one++;if(a[i] == 2 && b[i] != 2)two++;if(a[i] == 2 && b[i] == 1)repeat++;}cout<

#include
#include //sort()
using namespace std;
int a[1010];
int b[1010];int main()
{int n;cin>>n;for(int i = 0; i < n; ++i) {cin>>a[i];b[i] = a[i];}sort(a, a + n); //a[i]是排序后的，b[i]原排列int one = 0, two = 0, three = 0;for(int i = 0; i < n; ++i) {if(a[i] == 1 && b[i] != 1)one++;if(a[i] == 2 && b[i] == 3)two++;if(a[i] == 3 && b[i] == 2)three++;}cout<

9
2 2 1 3 3 3 2 3 1
410
2 2 2 3 1 1 1 1 3 2
5

8 3
1
4
7
3
1
2
4
3

6

#include
using namespace std;
int a[3010];int main()
{int n, m, sum, Min = 300000; //300000 = 3000 * 100cin>>n>>m;for(int i = 0; i < n; ++i) cin>>a[i];for(int i = 0; i < n - m + 1; ++i) { //这里是i < n - m + 1sum = 0;for(int j = i; j < i + m; ++j) { //这里是j < i + msum += a[j];}Min = min(Min, sum);}cout<

15 4
13 11 21 8 47 21 4 22 52 49 96 1 1 98 49
53

4 50
10 60
20 100
30 120
15 45

240.00

#include
#include //printf()
#include //sort()
using namespace std;
struct gold
{double w, p; //weight, price //要点1
};
bool cmp(gold x, gold y)
{return x.p * y.w > y.p * x.w; //要点2
}//防止精度缺失采取交叉相乘，虽然本题没什么用int main()
{struct gold a[110];int N, T;double ans = 0.00; //要点3cin>>N>>T;for(int i = 0; i < N; ++i)cin>>a[i].w>>a[i].p;sort(a, a + N, cmp);for(int i = 0; i < N; ++i) {if(T - a[i].w >= 0) {T -= a[i].w;ans += a[i].p;}else { //要点4ans += (T / a[i].w) * a[i].p;break;}}printf("%.2lf", ans);return 0;
}