第六篇博客——贪心策略
简单贪心
鸡兔同笼
🤔如果已知动物的头和腿的数量，如果要求最多动物数量的时候就优先考虑脚少的🐔，如果要求最少数量的时候优先考虑脚多的🐰。
FatMouse’ s Trade
在遇到类似于购物问题时，优先购买性价比高的东西，等到买不下来了再选择买部分（如果可以的话，实际上这也是能够简单贪心的前提——能够部分购买）。
Senior’ s Gun
题目大意：一个人有若干支枪，面对若干个怪物。枪有攻击力，怪物有防御力，一把枪只能最多干掉一只怪物，杀死怪物后，这个人可以获得攻击力-防御力的奖赏，请问最多的奖赏是多少（不必干掉所有怪物）。
🤔既然一支枪只能干掉一只怪物，所以贪心策略是每次都用最强的枪杀死最弱的怪物，以便让每一枪都能获得当前情况下的金额最大的奖金。
练习：代理服务器
链接：https://www.nowcoder.com/questionTerminal/1284469ee94a4762848816a42281a9e0
来源：牛客网
使用代理服务器能够在一定程度上隐藏客户端信息，从而保护用户在互联网上的隐私。我们知道n个代理服务器的IP地址，现在要用它们去访问m个服务器。这 m 个服务器的 IP 地址和访问顺序也已经给出。系统在同一时刻只能使用一个代理服务器，并要求不能用代理服务器去访问和它 IP地址相同的服务器（不然客户端信息很有可能就会被泄露）。在这样的条件下，找到一种使用代理服务器的方案，使得代理服务器切换的次数尽可能得少。
输入描述:
每个测试数据包括 n + m + 2 行。
第 1 行只包含一个整数 n，表示代理服务器的个数。
第 2行至第n + 1行每行是一个字符串，表示代理服务器的 IP地址。这n个 IP地址两两不相同。
第 n + 2 行只包含一个整数 m，表示要访问的服务器的个数。
第 n + 3 行至第 n + m + 2 行每行是一个字符串，表示要访问的服务器的 IP 地址，按照访问的顺序给出。
每个字符串都是合法的IP地址，形式为“xxx.yyy.zzz.www”，其中任何一部分均是0–255之间的整数。输入数据的任何一行都不包含空格字符。
其中，1<=n<=1000，1<=m<=5000。输出描述:
可能有多组测试数据，对于每组输入数据， 输出数据只有一行，包含一个整数s，表示按照要求访问服务器的过程中切换代理服务器的最少次数。第一次使用的代理服务器不计入切换次数中。若没有符合要求的安排方式，则输出-1。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <valarray>
#include <vector>
#include <set>
#include <unordered_set>
using namespace std;
int main() {
ios::sync_with_stdio(false);
int n, m;
while (cin >> n) {
//n个代理服务器
vector <string> proxies(n);
for (int i = 0; i < n; i++) {
cin >> proxies[i];
}
sort(proxies.begin(), proxies.end());
// 后面二分搜索用到
cin >> m;
//m个需要访问的服务器
vector <string> servers;
string s;
for (int i = 0; i < m; i++) {
cin >> s;
if (binary_search(proxies.begin(), proxies.end(), s)) {
// 如果需要请求的服务器非代理服务器，则一定不需要转换代理服务器，所以不考虑他们，只需考虑代理服务器需要被访问的情况
servers.push_back(s);
}
}
if (n == 1 && find(servers.begin(), servers.end(), proxies[0]) != servers.end()) {
//这个函数的意思：在servers向量中寻找proxies[0])，如果找到那就是迭代器不指向servers.end()，那这种情况是不可能安排好的
//<https://blog.csdn.net/e01528/article/details/89156964>
cout << -1 << endl;
continue;
}
// 模拟页表置换算法
unordered_set <string> st;
int ans = 0;
for (const string& server : servers) {
//C++ 11的语法 for(int a:b) 从数组b依次取出元素赋值给整型变量a，循环执行for中语句
if (st.count(server) == 0) {
//st中不能找到server就返回0，将server塞入st
if (st.size() == n - 1) { // 如果页面已满，有请求页不在页表，则进行置换
ans++;
st.clear();
}
st.insert(server);
}
}
cout << ans << endl;
}
return 0;
} 一个小tips：(dict.find(handle_str) != dict.end())比(dict.count(stmp) > 0)效率要高不少，不到一倍。
区间贪心
区间贪心，即有多个区间（比如时间），这些区间之间有的互相重叠，如何选择最多的互不重叠的区间即为区间贪心。
https://blog.csdn.net/Harington/article/details/87514015
今年暑假不AC
如何选择能够看到最多的电视节目？
- 优先选择开始时间最早的电视节目，不能满足
- 优先选择持续时间最短的节目，不能满足
- 综合上述两点，可以知道，优先选择结束时间早的就可以了
//将电视节目按照
#include <iostream>
#include<algorithm>
using namespace std;
struct show{
int st;
int end;
};
const int MAXN=100;
show arr[MAXN];
bool compare(show s1,show s2){
return s1.end<s2.end;
}
int main(){
while(cin>>n){
for(int i=0;i<n;i++){
cin>>arr[i].st>>arr[i].end;
}
sort(arr,arr+n,compare);
int t=0;
int ans=0;
for(int i=0;i<n;i++){
if(t<arr[i].st){
ans++;
t=arr[i].end;
}
}
cout<<ans<<endl;
}
return 0;
}
Case of Fugitive
题目大意：n个岛屿，在一条线上，岛屿有起点和终点，有m座桥，问能不能用其中的n-1座桥把岛屿连起来
思路：可以先把n个岛屿的位置，预处理成n-1个所需桥的长度范围，然后按照长度范围的最小值升序排列，把桥的长度按照升序排列并以桥开始选择区间，在满足的条件下，区间的max中最小的优先。
练习：To fill or Not to Fill
#include <iostream>
#include <cstdio>
#include <algorithm>
/*
50 1300 12 8
6.00 1250
7.00 600
7.00 150
7.10 0
7.20 200
7.50 400
7.30 1000
6.85 300
50 1300 12 2
7.10 0
7.00 600
749.17
The maximum travel distance = 1200.00
*/
using namespace std;
/*
输入 :
对于每种情况，第一行包含4个正数：Cmax（<=100），即油箱的最大容量；D（<=30000），
即杭州到目的地城市的距离；Davg（<=20），即汽车每单位汽油可行驶的平均距离；N（<=500），
即加油站总数。接下来是N行，每行包含一对非负数：Pi，煤气单价，Di（<=D），这个站到杭州的距离，i=1，…N。一行中的所有数字用空格隔开。
输出 :
对于每个测试用例，一行打印最便宜的价格，精确到小数点后2位。
假设开始时油箱是空的。如果无法到达目的地，请打印“最大行驶距离=X”，
其中X是车辆可以行驶的最大可能距离，精确到小数点后2位。
*/
struct GasStation {
double price;
int distance;
};
bool ComparePrice(GasStation x, GasStation y) {
return x.price < y.price;
}
int main() {
int cmax, d, davg, n; // cmax : 箱的最大容量, d : 州到目的地城市的距离, davg : 车每单位汽油可行驶的平均距离, n : 加油站总数;
while (cin >> cmax >> d >> davg >> n) {
double currentprice = 0; // 当前油费
bool tag[d + 1]; // 记录当前有哪段道路是从加油站出发能走的
GasStation gasStation[n];
for (int i = 1; i <= d; ++i) tag[i] = false;
for (int i = 0; i < n; ++i) cin >> gasStation[i].price >> gasStation[i].distance;
sort(gasStation, gasStation + n, ComparePrice); // 对油价按升序排
for (int i = 0; i < n; ++i) { // 对tag[]进行记录, 并同时计算出 currentprice
int currentdistance = 0; // 记录从这个加油站出发要用其油的距离
for (int j = gasStation[i].distance + 1; j <= gasStation[i].distance + cmax * davg; ++j) {
if (tag[j] == false) { // 如果 tag[j]为假则可走
tag[j] = true;
currentdistance++;
}
if (j == d || j == gasStation[i].distance + cmax * davg) { // 走到了尽头
currentprice += gasStation[i].price * currentdistance / (davg * 1.0);
break;
}
}
}
int fill = 1; // tag[]是否全为真的标志位
double journey = 0;
for (int i = 1; i <= d; ++i) {
if (tag[i] == true) journey++;
else {
fill = 0;
break;
}
}
if (fill) printf("%.2f\n",currentprice);
else printf("The maximum travel distance = %.2f\n", journey);
}
return 0;
} 
京公网安备 11010502036488号