🍦🍦🍦由于代码都是我自己敲出来调试的，所以可能不能一次更新那么多，大家见谅，不过因为我最近在备考机试，所以会拿出大量的时间在这上边，更新的会比较勤的~~~
目录
🧊🧊🧊2.7 查找类问题
🥥题型总结：
🥥例题：DreamJudge 1476
🥥例题：DreamJudge 1477
🥥练习题目：
DreamJudge 1177 查找学生信息
DreamJudge 1388 查找 1
DreamJudge 1387 查找 - 北邮 🍰
DreamJudge 1383 查找第 K 小数
🧊🧊🧊2.8 贪心类问题
🥥例题：DreamJudge 1478
🥥题型总结：
🥥练习题目：
DreamJudge 1307 组队刷题 🍰
DreamJudge 1347 To Fill or Not to Fill 🍰
🧊🧊🧊2.9 链表类问题
🥥题型总结：
🥥例题：DreamJudge 1081
🥥练习题目：
DreamJudge 1015 单链表
DreamJudge 1018 击鼓传花
DreamJudge 1025 合并链表
DreamJudge 1405 遍历链表
🧊🧊🧊2.7 查找类问题
🥥题型总结：
- 数字查找： 给你一堆数字，让你在其中查找 x 是否存在（ 如果 x 存在，请输出有几个）
- 字符串查找： 给你很多个字符串，让你在其中查找字符串 s 是否存在
当查询次数很多或数据量特别大的时候就不适合用顺序查找了。这类查找类题目，推荐使用map！
🥥例题：DreamJudge 1476
对于查询量大的题目，我们有两种方法：一是将学号先排好序，然后使用二分查找，但是很多同学写二分的时候容易出现问题，而且代码量也比较大，不太推荐这种做法。二是使用map，推荐大家使用这种方法，基本上 map 可以通过 99.9%的这类题目。
#include <bits/stdc++.h>
using namespace std;
struct node{string num;string name;string sex;int age;
};
int main(){int n,q;map<string, node> M;//定义一个 map 映射while(scanf("%d", &n)!=EOF){for(int i=0;i<n;i++){node tmp;cin>>tmp.num>>tmp.name>>tmp.sex>>tmp.age;M[tmp.num] = tmp;//将学号指向对应的结构体}scanf("%d", &q);for(int i=0;i<q;i++){string num;cin>>num;if((M.find(num))!=M.end())//find 查找 如果找不到则返回末尾cout<<M[num].num<<" "<<M[num].name<<" "<<M[num].sex<<" "<<M[num].age<<endl;elsecout<<"No Answer!"<<endl;}}return 0;
}上边是静态查找，接下来我们看一道动态查找的问题：
🥥例题：DreamJudge 1477
分析这道题目，这道题的一大特点就是，数的集合在不断的改变。如果用先排序再二分的方法就会很困难，因为加入新的数时需要去多次移动数组才能将数插进去，最坏情况每次插入都是 O(n)的复杂度，这是无法接受的。当然也不是说不能用这样的方法来解决，可以用离线的方法来解决这个问题，但是这样做太复杂，不适合在考试中使用。那么我们考虑用 map 来解决这个问题。
#include <bits/stdc++.h>
using namespace std;
int main(){int n,q,x;map<int, int> M;//定义一个 map 映射scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &x);M[x]++;//记录集合中 x 有多少个}scanf("%d", &q);for (int i = 0; i < q; i++) {scanf("%d", &x);if (M[x] == 0) {//如果 x 的个数为 0printf("no\n");M[x]++;//将 x 加入到集合中}else printf("find\n");}return 0;
}接下来还是说说二分这个方法，二分的前提是单调性，只要满足单调性就可以二分，不论是单个元素还是连续区间。下面给出二分的代码供参考：
#include <bits/stdc++.h>
using namespace std;
int a[10005];
int main(){int n,x;scanf("%d", &n);//输入 n 个数for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);}sort(a+1, a+1+n);//排序保持单调性scanf("%d", &x);//要查找的数 x 13. int l = 1, r = n;while (l <= r) {int mid = (l + r) / 2;if (a[mid] == x) {printf("find\n");return 0;}if (a[mid] > x) {//如果 x 比中间数小r = mid - 1;//说明在左区间}else l = mid + 1;//否则在右区间内}printf("not find\n");return 0;
}🥥练习题目：
DreamJudge 1177 查找学生信息
这道题目其实不用map，直接使用两个数组，一个数组记录每个人借阅了哪本书，另一个数组记录每本书的借阅情况，然后查找即可。
#include<bits/stdc++.h>
using namespace std;
int main()
{int n,m;while(cin>>n>>m){vector<int> a(n+5),b(m+5);for(int i=1;i<=n;i++){cin>>a[i];b[a[i]]++;}for(int i=1;i<=n;i++){if(b[a[i]]-1) cout<<b[a[i]]-1<<endl;else cout<<"BeiJu"<<endl;}}return 0;
}DreamJudge 1388 查找 1
这道题目用不到map，因为只需要记录一个数据，直接使用set进行查找即可，也是用find进行查找，如果需要记录二维信息，那么用map。
#include<bits/stdc++.h>
using namespace std;
int main()
{int n,m;while(cin>>n){set<int> s;int cur;for(int i=0;i<n;i++){cin>>cur;s.insert(cur);}cin>>m;for(int i=0;i<m;i++){cin>>cur;if(s.find(cur)!=s.end()) cout<<"YES"<<endl;else cout<<"NO"<<endl;}}return 0;
}DreamJudge 1387 查找 - 北邮 🍰
#include<iostream>
#include<string>
using namespace std;
string s;
int n;void pd1(int i,int len)
{int left=i,right=i+len-1;//翻转范围for (int j=1;j<=len/2;j++){char tmp=s[left];s[left]=s[right];s[right]=tmp;left++;right--;}
}int main()
{while(cin>>s){cin>>n;while(n--){string op;cin>>op;int i=op[1]-'0';int len=op[2]-'0';if(op[0]-'0'==0) pd1(i,len);else {string rep=op.substr(3,op.size());s.erase(i,len);s.insert(i,rep);}cout<<s<<endl;}}return 0;
}DreamJudge 1383 查找第 K 小数
#include<bits/stdc++.h>
using namespace std;
int main()
{int n,k,cur;set<int> s;while(cin>>n){for(int i=0;i<n;i++) {cin>>cur;s.insert(cur);}cin>>k;k--;auto it=s.begin();while(k--) it++;cout<<*it<<endl;}return 0;
}🧊🧊🧊2.8 贪心类问题
贪心算法更重要的是一种贪心的思想，它是通过当前最优解，得到全局最优解。
我们先通过几个例子感受一下贪心思想：
例子 1：地上有 3 张纸币，分别是 5 元、1 元和 10 元，问你只能拿一张，最多能拿多少钱？
解析：很明显，10 元。
例子 2：地上有 n 张纸币，有 1 元的，有 5 元的，还要 10 元的，问你只能拿一张，最多能拿多少钱？
解析：很明显，还是 10 元。
例子 3：地上有很多纸币，有 a 张 1 元的，有 b 张 5 元的，还要 c 张 10 元的，问你从中拿x张，最多能拿多少钱？
解析：大家应该都能想到，肯定是优先拿 10 元的，如果 10 元的拿完了，再拿 5 元的，最后才会拿 1 元的。这就是贪心的思想，所以贪心其实是很容易想到的。
例子 4：有 n 个整数构成的集合，现在从中拿出 x 个数来，问他们的和最大能是多少？
解析：相信大家都能想到，优先拿大的，从大到小一个个拿，这样组成的和最大。那么在解决这个问题之前，我们需要先排序，从大到小的排好序，然后将前 x 个数的和累加起来就是答案。
使用贪心时，往往需要按照某个特性先排好序，所以贪心一般和sort、堆等一起使用。
🥥例题：DreamJudge 1478
通过分析可以发现，小明想要喝尽量多的饮料，肯定优先选择性价比最高的饮料喝，也就是说先喝1毫升的价格最低的饮料，所以就需要去比较每种饮料1毫升的价格是多少，按照这个单价从低到高依次排序，然后一个一个往后喝，这样可以保证小明能喝到最多的饮料。
#include <bits/stdc++.h>
using namespace std;
struct node {double w, m;
}p[1005];
bool cmp(node a, node b) {
//按照每毫升的价格从低到高排序return a.w/a.m < b.w/b.m;
}
int main(){int n,x;while (scanf("%d%d", &x, &n) != EOF) {if (x == -1 && n == -1) break;for (int i = 1; i <= n; i++) {scanf("%lf%lf", &p[i].m, &p[i].w);}sort(p+1, p+1+n, cmp);double ans = 0;for (int i = 1; i <= n; i++) {if (x >= p[i].w) {//如果剩余的钱能全买ans += p[i].m;x -= p[i].w;}else {//如果剩余的钱买不完这种饮料ans += (p[i].m*x/p[i].w);break;//到这里 x 已经为 0 了}}printf("%.3lf\n", ans);}return 0;
}🥥题型总结：
贪心题目看起来简单但做起来难的原因原因有二：一是就没有想到这个题目应该用贪心算法，没能将题目抽象成数学模型来分析。二是读懂题了，知道应该用贪心算法解题，但排序的特征点没有找准，因为不是所有题目都能明显看出从小到大排序，有的题目可能隐藏的比较深，但是这种难度的贪心不常见。所以机试中的贪心题，只要反应过来是用贪心，99%的情况下都能解决。
🥥练习题目：
DreamJudge 1307 组队刷题 🍰
#include<bits/stdc++.h>
using namespace std;
struct node
{double w;//题目double m;//精力
}a[200];
bool cmp(node a,node b){ return a.w/a.m>b.w/b.m;}
int main()
{int m,n;while(cin>>m>>n){if(m==-1&&n==-1)break;for(int i=0;i<n;i++) cin>>a[i].w>>a[i].m;sort(a,a+n,cmp);double cnt=0;for(int i=0;i<n;i++){if(m>a[i].m){m-=a[i].m;cnt+=a[i].w;}else{cnt+=m/a[i].m*a[i].w;break;}}printf("%.3lf\n",cnt);//用cout<<fixed<<setpercision(3)<<cnt会超时}return 0;
}DreamJudge 1347 To Fill or Not to Fill 🍰
输出：
749.17 The maximum travel distance = 1200.00
/*
摘自N诺评论区大神：mimicool
我们假设会经过所有的加油站
我们可以假装持有价格高得油，一旦遇到价格低的就进行替换
在经过加油站的时候，我们补充该加油站的油（注意是假设补充，具体是否补充要看之后有没有遇见更加便宜的油）比如，我们的油箱在遇到价值4快的加油站时，还剩下2块钱的油和5块钱的油，这说明之前假装补充的5块钱的油是可以被四块钱的油所替代，因此我们就可以补充油注意计算cost的时候要以实际花费的油为准，而不是在补充油的时候进行计算
*/#include<bits/stdc++.h>
using namespace std;// double判断相等需要用一个接近无穷小
#define eps 1e-8//加油站结构体
struct Station{double price, distance;
}s[200];bool cmp(Station s1, Station s2){return s1.distance < s2.distance;
}int main(){double cmax, d, davg;int n;while (scanf("%lf%lf%lf%d", &cmax, &d, &davg, &n) != EOF){// 从1开始，较为清晰for (int i = 1; i <= n; i++){scanf("%lf%lf", &s[i].price, &s[i].distance);}//终点看作特殊的加油站s[n+1].distance = d;s[n+1].price = 0;//注意这里的上下界sort(s+1, s+1+n+1, cmp);//双端队列，一方面弹出最低价格的油作为消耗；另一方面弹出最高价格的油作为替换deque<pair<double, double>> d;double sumdis = 0., cost = 0.;if (s[1].distance > eps) printf("The maximum travel distance = 0.00\n");else {d.push_back(make_pair(s[1].price, cmax));for (int i = 2; i <= n+1; i++){//目标第i个加油站double sdis = s[i].distance - s[i-1].distance; //距离目标加油站的距离double need = sdis / davg; //需要使用的油//printf("%d, %lf, %lf\n", i, sdis, need);if (need-cmax > eps){//油不够用sumdis += cmax*davg;printf("%s%.2lf", "The maximum travel distance = ", sumdis);break;}else{//油够用sumdis += sdis;//add是最后要添加的油，计算过程：使用的油+高价的油double add = need;while (need > eps){//这部分是用来计算cost和更新队列原有油信息的if (d.front().second-need > eps){//需求小于价格最低的油量，意味着无需弹出队列cost += need*d.front().first;d.front().second -= need;need = 0;}else {//需求大于价格最低的油量，意味着需要弹出队列并进行循环cost += d.front().first*d.front().second;need -= d.front().second;d.pop_front();}}while(!d.empty() && d.back().first > s[i].price){//这部分使用while循环遍历，找出所有高价油弹出add += d.back().second;d.pop_back();}//用当前加油站油替换d.push_back(make_pair(s[i].price, add));}//如果此时到达了终点，就打印costif (i == n+1) printf("%.2lf\n", cost);}}}return 0;
}
🧊🧊🧊2.9 链表类问题
链表类问题属于选读章节，对于使用 OJ 测评的院校的同学来说，这类问题可以用数组来实现，没有必要用链表去实现，慢且易出错，所以一般都直接用数组实现，反正最后能 AC 就行，这部分同学跳过本节或仅做了解即可。但是对于非 OJ 测评的院校来说，链表类问题可以说是必考的题型。
🥥题型总结：
- 猴子报数：循环链表建立之后，按照题意删除节点。
- 两个有序链表合并为一个：这个和两个有序数组合并为一个有序数组原理一样。
- 链表排序：使用冒泡排序进行链表排序，因为冒泡排序是相邻两个元素进行比较交换，适合链表。
🥥例题：DreamJudge 1081
需要创建一个首尾相连的循环链表，先走 s 步，再开始循环遍历链表，每走 m 步删除一个节点，直到链表中只剩下一个节点时结束循环。只剩一个节点的判断条件是，它的下一个指针指向的是自己，说明自循环了。
#include <stdio.h>
#include <malloc.h>
struct node {int num;struct node *next;
};
int n, s, m;
//创建循环链表
struct node* create() {struct node *head, *now, *pre;for (int i = 1; i <= n; i++) {now = (struct node *)malloc(sizeof(node));if (i == 1) {head = now;pre = now;}now->num = i;now->next = head;pre->next = now;pre = now;}return head;
};
//按照题目要求输出
void print(struct node *head) {struct node *p, *pre;//pre 是前一个节点p = head;s -= 1;//因为起点在第一个 所以要少走一步while (s--) {//先走 s 步pre = p;p = p->next;}int i = 1;while (p != NULL) {if (p == p->next) {//只剩最后一个printf("%d\n", p->num);break;}if (i % m == 0) {//找到第 m 个printf("%d,", p->num);//输出它pre->next = p->next;//删除它}else pre = p;//这里一定要用 else 如果是删除的话 pre 不变p = p->next;i++;}
}
int main(){while (scanf("%d%d%d", &n, &s, &m) != EOF) {if (n==0&&s==0&&m==0) break;struct node *head;head = create();print(head);}return 0;
}🥥练习题目：
DreamJudge 1015 单链表
#include<bits/stdc++.h>
using namespace std;
int main()
{int a[10]={0};for(int i=0;i<5;i++) cin>>a[i];sort(a,a+5);for(int i=0;i<5;i++) cout<<a[i]<<" ";return 0;
}DreamJudge 1018 击鼓传花
#include<bits/stdc++.h>
using namespace std;
int main()
{int n;cin>>n;queue<int> q;int cur;for(int i=1;i<=n;i++) q.push(i);while(!q.empty()){for(int i=0;i<2;i++){int c=q.front();q.pop();q.push(c);}cur=q.front();q.pop();}cout<<cur;return 0;
}DreamJudge 1025 合并链表
#include<bits/stdc++.h>
using namespace std;
int main()
{vector<int> a;int n,m,cur;cin>>n;for(int i=0;i<n;i++) {cin>>cur;a.push_back(cur);}cin>>m;for(int i=0;i<m;i++){cin>>cur;a.push_back(cur);}sort(a.begin(),a.end());for(int i=0;i<n+m;i++) cout<<a[i]<<" ";return 0;
}DreamJudge 1405 遍历链表
#include<bits/stdc++.h>
using namespace std;
int main()
{int n,a[1010]={0};cin>>n;for(int i=0;i<n;i++) cin>>a[i];sort(a,a+n);for(int i=0;i<n;i++) cout<<a[i]<<" ";return 0;
}创作不易，点个赞吧~点赞收藏不迷路，感兴趣的宝子们欢迎关注该专栏~
勤奋努力的宝子们，学习辛苦了！🌷🌷🌷休息下，我们下部分再见👋( •̀ ω •́ )✧~
：深入MySQL高级语法，提升开发效率)
