算法基础知识——贪心策略

目录：

1. 基础知识
   1. 贪心策略（自顶向下设计、局部最优、无后效性、最优子结构）
   2. 活动选择问题
   3. 动态规划算法和贪心算法区别
2. 应用实例
   1. 鸡兔同笼【北京大学】
   2. FatMouse' Trade【王道机试】
   3. Senior's Gun【王道机试】
   4. 代理服务器【清华大学】
   5. 今年暑假不AC【王道机试】
   6. Case of Fugitive【Codeforces】
   7. To Fill or Not to Fill【浙江大学】

一、基础知识

1、贪心策略：

• 定义：总是做出局部最优的选择。对于特定的最优化问题，贪心策略保证一定能够收敛到全局最优解。
• 贪心算法自顶向下的设计：做出一个选择，然后求解剩下的那个子问题，而不是自底向上地求解出很多子问题，然后再做出选择。
• 术语定义：
  • 无后效性：某个状态以前的过程不会影响以后的状态，而只与当前状态有关。
  • 最优子结构：如果一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质。
• 核心思想：总是选择当前状态下最优的策略。并不以整体最优进行考虑，而只考虑当前这一步，可获得局部最优解。
• 应用场景：
  • 在遇到求最大、最小、最多等多值问题时，应优先考虑用贪心策略求解。
  • 若问题满足最优子结构性质，即该问题无后效性，那么全局的最优解便可由求子问题的最优解得到。
• 常见题型：
  • 简单贪心
  • 区间贪心：当有多个不同的区间存在，且这些区间有可能相互重叠的时候，如何选择才能从众多区间中，选取最多的两两互不相交的区间。
• 贪心算法设计过程：
  • 确定问题的最优子结构
  • 设计一个递归算法
  • 证明如果我们做出一个贪心选择，只剩下一个子问题
  • 证明做出贪心选择后，原问题总是存在最优解，即贪心选择总是安全的
  • 设计一个递归算法实现贪心策略
  • 将递归算法转换为迭代算法

2、活动选择问题：

• 问题描述：一个调度竞争共享资源的多个活动的问题，目标是选出一个最大的互相兼容的活动集合。
  • 兼容定义：每个活动Ai都有一个开始时间Si和结束时间Fi，如果被选中，任务Ai发生在[ Si, Fi )期间。如果两个活动Ai和Aj满足[ Si, Fi )和[ Sj, Fj )不重叠，则称它们是兼容的。
• 在动态规划策略中，有：
  • c[i, j] = 0，若Sij = ∅
  • c[i, j] = max{ c[i, k] + c[k, j] + 1}，若Sij ≠ ∅
• 在贪心策略中：
  • 思路：
    • 首先应该选择这样一个活动，选出它后剩下的资源应能被尽量多的其他任务所用。因此可以选择最早结束的活动，记为A1。
    • 然后选择在A1结束后开始的活动。

3、动态规划算法和贪心算法区别：

• 动态规划算法先求解子问题才能进行第一次选择；贪心算法在进行第一次选择之前不求解任何子问题。
• 动态规划算法是自底向上进行计算的（如果自顶向下求解，需要建立备忘机制）；贪心算法通常是自顶向下的，进行一次又一次选择，将给定问题实例变得更小。
• 动态规划算法的选择通常依赖于子问题的解，贪心算法的选择可能依赖于之前做出的选择，但不依赖于任何将来的选择或者子问题的解。

二、应用实例

1、题目描述：一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物。【北京大学】

• 输入格式：每组测试数据占1行，每行一个正整数a (a < 32768)
• 输出格式：输出包含n行，每行对应一个输入,包含两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用一个空格分开。如果没有满足要求的答案，则输出两个0。
• 样例输入：
  • 2
  • 3
  • 20
• 样例输出：
  • 0 0
  • 5 10

示例代码1：

#include <iostream>

using namespace std;

const int RABBIT_FOOT = 4;
const int CHICKEN_FOOT = 2;

int main(){
	int foot;
	while(cin >> foot){
		int tmp1 = foot, tmp2 = foot;
		int most = 0, less = 0;
		while(tmp1 >= CHICKEN_FOOT){
			most++;
			tmp1 -= CHICKEN_FOOT;
		}
		while(tmp2 >= RABBIT_FOOT){
			less++;
			tmp2 -= RABBIT_FOOT;
		}
		while(tmp2 >= CHICKEN_FOOT){
			less++;
			tmp2 -= CHICKEN_FOOT;
		}
		if(tmp1 == 0 && tmp2 == 0){
			cout << less << " " << most << endl;
		}else{
			cout << "0 0" << endl;
		}
	}
	return 0;
}

示例代码2：

#include <iostream>

using namespace std;

int main(){
	int foot;
	while(cin >> foot){
		int most = 0, less = 0;
		if(foot % 2 == 0){
			most = foot / 2;
			less = foot / 4 + (foot % 4) / 2;
		}
		cout << less << " " << most << endl;
	}
	return 0;
}

2、题目描述：FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean. The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get J[i]* a% pounds of JavaBeans if he pays F[i]* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain. 【王道机试】

• 输入格式：The input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers J[i] and F[i] respectively. The last test case is followed by two -1's. All integers are not greater than 1000.
• 输出格式：For each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain. 
• 样例输入：
  • 5 3
  • 7 2
  • 4 3
  • 5 2
  • 20 3
  • 25 18
  • 24 15
  • 15 10
  • -1 -1
• 样例输出：
  • 13.333
  • 31.500

示例代码：

#include <iostream>
#include <queue>
#include <iomanip>

using namespace std;

struct Mouse{
	double javabean;
	double catF;
	Mouse(double j, double c):javabean(j), catF(c){};
};

bool operator<(const Mouse &m1, const Mouse &m2){
	if(m1.catF == 0 && m2.catF == 0){
		return m1.javabean < m2.javabean;
	}
	if(m1.catF == 0){
		return false;
	}
	if(m2.catF == 0){
		return true;
	}
	return m1.javabean / m1.catF < m2.javabean / m2.catF;
}

priority_queue<Mouse> myQueue;

int main(){
	double M, N;
	while(cin >> M >> N && M != -1 && N != -1){
		double f, j;
		for(int i = 0; i < N; i++){
			cin >> j >> f;
			Mouse mouse(j, f);
			myQueue.push(mouse);
		}
		double answer = 0;
		while(M >= 0 && myQueue.size() > 0){
			if(M - myQueue.top().catF >= 0){
				M -= myQueue.top().catF;
				answer += myQueue.top().javabean;
				myQueue.pop();
			}else{
				answer += M * (myQueue.top().javabean / myQueue.top().catF);
				break;
			}
		}
		cout << fixed << setprecision(3) << answer << endl;
		if(!myQueue.empty()){
			myQueue.pop();
		}
	}
	return 0;
}

3、题目描述：Xuejiejie is a beautiful and charming sharpshooter.She often carries n guns, and every gun has an attack power a[i].One day, Xuejiejie goes outside and comes across m monsters, and every monster has a defensive power b[j].Xuejiejie can use the gun i to kill the monster j, which satisfies b[j] ≤ a[i], and then she will get a[i]-b[j] bonus.Remember that every gun can be used to kill at most one monster, and obviously every monster can be killed at most once.Xuejiejie wants to gain most of the bonus. It's no need for her to kill all monsters.【王道机试】

• 输入格式：In the first line there is an integer T, indicates the number of test cases.In each case:The first line contains two integers n,m.The second line contains n integers, which means every gun's attack power.The third line contains m integers, which mean every monster's defensive power.1 ≤ n,m ≤ 100000, -10^9 ≤ a[i],b[j] ≤ 10^9.
• 输出格式：For each test case, output one integer which means the maximum of the bonus Xuejiejie could gain.
• 样例输入：
  • 1
  • 2 2
  • 2 3
  • 2 2
• 样例输出：
  • 1

示例代码：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> monster;
vector<int> gun;

int main(){
	int number;
	while(cin >> number){
		int n, m, monsterPower, gunPower;
		for(int i = 0; i < number; i++){
			cin >> n >> m;
			for(int j = 0; j < n; j++){
				cin >> gunPower;
				gun.push_back(gunPower);
			}
			for(int j = 0; j < m; j++){
				cin >> monsterPower;
				monster.push_back(monsterPower);
			}
			sort(gun.begin(), gun.end());
			sort(monster.begin(), monster.end());
			int bonus = 0, loc = 0;
			bool flag = false;
			//强枪杀弱怪
			for(int j = gun.size() - 1; j >= 0; j--){
				if(loc == monster.size() || flag){  //杀到最后一只怪了
					break;
				}
				if(monster[loc] <= gun[j]){
					bonus += gun[j] - monster[loc];
					loc++;
				}else{  //你打不过任何一只怪了
					flag = true;
				}
			}
			cout << bonus << endl;
			monster.clear();
			gun.clear();
		}
	}
	return 0;
}

4、题目描述：使用代理服务器能够在一定程度上隐藏客户端信息，从而保护用户在互联网上的隐私。我们知道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。
• 样例输入：
  • 3
  • 166.111.4.100
  • 162.105.131.113
  • 202.112.128.69
  • 6
  • 72.14.235.104
  • 166.111.4.100
  • 207.46.19.190
  • 202.112.128.69
  • 162.105.131.113
  • 118.214.226.52
• 样例输出：
  • 1

示例代码：

#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<string> serverAddress;
vector<string> agentAddress;

int main(){
	int n, serverCount;
	while(cin >> n){
		string ip;
		for(int i = 0; i < n; i++){
			cin >> ip;
			agentAddress.push_back(ip);
		}
		cin >> serverCount;
		for(int i = 0; i < serverCount; i++){
			cin >> ip;
			serverAddress.push_back(ip);
		}
		int answer = 0;
		bool flag = false;
		for(int i = 0; i < serverAddress.size(); ){
			int maxCount = 0;
			for(int j = 0; j < agentAddress.size(); j++){
				int count = 0, tmp = i;
				while(tmp < serverAddress.size() && serverAddress[tmp] != agentAddress[j]){
					count++;
					tmp++;
				}
				if(count > maxCount){
					maxCount = count;
				}
			}
			if(maxCount == 0){
				flag = true;
				break;
			}
			i += maxCount;
			answer++;
		}
		if(flag){
			cout << -1 << endl;
		}else{
			cout << answer - 1 << endl;
		}
		serverAddress.clear();
		agentAddress.clear();
	}
	return 0;
}

5、题目描述：“今年暑假不AC？”
“是的。”
“那你干什么呢？”
“看世界杯呀，笨蛋！”
确实如此，世界杯来了，球迷的节日也来了，估计很多ACMer也会抛开电脑，奔向电视了。
作为球迷，一定想看尽量多的完整的比赛，当然，作为新时代的好青年，你一定还会看一些其它的节目，如《新闻联播》（永远不要忘记关心国家大事）、《非常6+7》、《超级女生》，以及王小丫的《开心辞典》等等，假设你已经知道了所有你喜欢看的电视节目的转播时间表，你会合理安排吗？（目标是能看尽量多的完整节目）【王道机试】

• 输入格式：输入数据包含多个测试实例，每个测试实例的第一行只有一个整数n(n<=100)，表示你喜欢看的节目的总数，然后是n行数据，每行包括两个数据Ti_s,Ti_e (1<=i<=n)，分别表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。n=0表示输入结束，不做处理。
• 输出格式：对于每个测试实例，输出能完整看到的电视节目的个数，每个测试实例的输出占一行。
• 样例输入：
  • 12
  • 1 3
  • 3 4
  • 0 7
  • 3 8
  • 15 19
  • 15 20
  • 10 15
  • 8 18
  • 6 12
  • 5 10
  • 4 14
  • 2 9
  • 0
• 样例输出：
  • 5

示例代码：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct TV{
	int startTime;
	int endTime;
	TV(int s, int e):startTime(s), endTime(e){};
};

vector<TV> tvList;

bool CompareAsc(const TV &t1, const TV &t2){
	if(t1.endTime == t2.endTime){
		return t1.startTime > t2.startTime;
	}else{
		return t1.endTime < t2.endTime;
	}
}

int main(){
	int n;
	while(cin >> n && n != 0){
		int st, et;
		for(int i = 0; i < n; i++){
			cin >> st >> et;
			TV tv(st, et);
			tvList.push_back(tv);
		}
		sort(tvList.begin(), tvList.end(), CompareAsc);
		int answer = 0, currentTime = 0;
		for(int i = 0; i < tvList.size(); i++){
			if(currentTime <= tvList[i].startTime){
				answer++;
				currentTime = tvList[i].endTime;
			}
		}
		cout << answer << endl;
		tvList.clear();
	}
	return 0;
}

6、题目描述：Andrewid the Android is a galaxy-famous detective. He is now chasing a criminal hiding on the planet Oxa-5, the planet almost fully covered with water.
The only dry land there is an archipelago of n narrow islands located in a row. For more comfort let's represent them as non-intersecting segments on a straight line: island i has coordinates [l i , r i ], besides, r i  < l i + 1 for 1 ≤ i ≤ n - 1.
To reach the goal, Andrewid needs to place a bridge between each pair of adjacent islands. A bridge of length a can be placed between the i -th and the (i + 1)-th islads, if there are such coordinates of x and y , that l i  ≤ x ≤ r i , l i + 1 ≤ y ≤ r i + 1 and y - x = a .
The detective was supplied with m bridges, each bridge can be used at most once. Help him determine whether the bridges he got are enough to connect each pair of adjacent islands.【Codeforces】

• 输入格式：The first line contains integers n (2 ≤ n ≤ 2*10^5) and m (1 ≤ m ≤ 2*10^5) — the number of islands and bridges.
  Next n lines each contain two integers li and ri (1 ≤ li ≤ ri ≤ 10^18) — the coordinates of the island endpoints.
  The last line contains minteger numbers a1, a2, ..., am (1 ≤ ai ≤ 10^18) — the lengths of the bridges that Andrewid got.
• 输出格式：If it is impossible to place a bridge between each pair of adjacent islands in the required manner, print on a single line "No" (without the quotes), otherwise print in the first line "Yes" (without the quotes), and in the second line print n - 1 numbers b1, b2, ..., bn - 1, which mean that between islands i and i + 1 there must be used a bridge number bi. 
  If there are multiple correct answers, print any of them. Note that in this problem it is necessary to print "Yes" and "No" in correct case.
• 备注：In the first sample test you can, for example, place the second bridge between points 3 and 8, place the third bridge between points 7 and 10 and place the first bridge between points 10 and 14.In the second sample test the first bridge is too short and the second bridge is too long, so the solution doesn't exist.
• 样例输入：
  • 4 4
  • 1 4
  • 7 8
  • 9 10
  • 12 14
  • 4 5 3 8
  • 2 2
  • 11 14
  • 17 18
  • 2 9
  • 2 1
  • 1 1
  • 1000000000000000000 1000000000000000000
  • 999999999999999999
• 样例输出：
  • Yes
  • 2 3 1 
  • No
  • Yes
  • 1 

示例代码：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct Island{
	long long bLeft;
	long long bRight;
	int index;
	Island(long long bl, long long br, int i):bLeft(bl), bRight(br),index(i){};
};

struct TwoIslandDistance{
	long long minLength;
	long long maxLength;
	int index;
	TwoIslandDistance(long long min, long long max, int i):minLength(min), maxLength(max), index(i){};
};

struct Bridge{
	int index;
	long long bridgeLength;
	Bridge(int i, long long b):index(i), bridgeLength(b){};
};

struct Answer{
	int bridgeIndex;
	int islandIndex;
	Answer(int b, int i):bridgeIndex(b), islandIndex(i){};
};

vector<Island> islandList;
vector<TwoIslandDistance> distanceList;
vector<Bridge> bridgeList;
vector<Answer> answerList;

bool IslCompareAsc(const Island &i1, const Island &i2){
	return i1.bLeft < i2.bLeft;
}

bool DisCompareAsc(const TwoIslandDistance &t1, const TwoIslandDistance &t2){
	if(t1.minLength == t2.minLength){
		return t1.maxLength < t2.maxLength;
	}else{
		return t1.minLength < t2.minLength;
	}
}

bool BriCompareAsc(const Bridge &b1, const Bridge &b2){
	return b1.bridgeLength < b2.bridgeLength;
}

bool AnswerCompareAsc(const Answer &a1, const Answer &a2){
	return a1.islandIndex < a2.islandIndex;
}

int main(){
	int bridgeNumber, islandNumber;
	long long bLength, iLeft ,iRight;
	while(cin >> islandNumber >> bridgeNumber){
		for(int i = 0; i < islandNumber; i++){
			cin >> iLeft >> iRight;
			Island island(iLeft, iRight, i);
			islandList.push_back(island);
		}
		sort(islandList.begin(), islandList.end(), IslCompareAsc);
		long long min, max;
		for(int i = 0; i < islandList.size() - 1; i++){
			min = islandList[i + 1].bLeft - islandList[i].bRight;
			max = islandList[i + 1].bRight - islandList[i].bLeft;
			TwoIslandDistance distance(min, max, i);
			distanceList.push_back(distance);
		}
		sort(distanceList.begin(), distanceList.end(), DisCompareAsc);
		for(int i = 1; i <= bridgeNumber; i++){
			cin >> bLength;
			Bridge bridge(i, bLength);
			bridgeList.push_back(bridge);
		}
		sort(bridgeList.begin(), bridgeList.end(), BriCompareAsc);
		bool flag = false;
		int loc = 0;
		for(int i = 0; i < bridgeList.size(); i++){
			if(bridgeList[i].bridgeLength <= distanceList[loc].maxLength 
				&& bridgeList[i].bridgeLength >= distanceList[loc].minLength){
					Answer answer(bridgeList[i].index, distanceList[loc].index);
					answerList.push_back(answer);
					loc++;
			}
			if(loc == distanceList.size()){
				flag = true;
				break;
			}
		}
		if(flag){
			cout << "Yes" << endl;
			sort(answerList.begin(), answerList.end(), AnswerCompareAsc);
			for(int i = 0; i < answerList.size(); i++){
				cout << answerList[i].bridgeIndex << " ";
			}
			cout << endl;
		}else{
			cout << "No" << endl;
		}
		bridgeList.clear();
		distanceList.clear();
		answerList.clear();
		islandList.clear();
	}
	return 0;
}

7、题目描述：With highways available, driving a car from Hangzhou to any other city is easy. But since the tank capacity of a car is limited, we have to find gas stations on the way from time to time. Different gas station may give different price. You are asked to carefully design the cheapest route to go.【浙江大学】

• 输入格式：For each case, the first line contains 4 positive numbers: Cmax (<= 100), the maximum capacity of the tank; D (<=30000), the distance between Hangzhou and the destination city; Davg (<=20), the average distance per unit gas that the car can run; and N (<= 500), the total number of gas stations. Then N lines follow, each contains a pair of non-negative numbers: Pi, the unit gas price, and Di (<=D), the distance between this station and Hangzhou, for i=1,...N. All the numbers in a line are separated by a space.
• 输出格式：For each test case, print the cheapest price in a line, accurate up to 2 decimal places. It is assumed that the tank is empty at the beginning. If it is impossible to reach the destination, print "The maximum travel distance = X" where X is the maximum possible distance the car can run, accurate up to 2 decimal places.
• 样例输入：
  • 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

示例代码：

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

struct Station{
	double gasPrice;
	double statDist;
	Station(double g, double d):gasPrice(g), statDist(d){};
};

bool CompareAsc(const Station &s1, const Station &s2){
	if(s1.statDist == s2.statDist){
		return s1.gasPrice < s2.gasPrice;
	}else{
		return s1.statDist < s2.statDist;
	}
}

int main(){
	vector<Station> statList;
	double tankSize, distance, distPerOil, station;
	while(cin >> tankSize >> distance >> distPerOil >> station){
		double gasPrice, distStation;
		for(int i = 0; i < station; i++){
			cin >> gasPrice >> distStation;
			Station s(gasPrice, distStation);
			statList.push_back(s);
		}
		sort(statList.begin(), statList.end(), CompareAsc);
		double maxDist = tankSize * distPerOil;
		double price = 0.0, currDist = 0.0, currTankSize = 0.0;
		int currStat = 0;
		double maxArrive = 0.0;
		bool flag = true; //能到达目的地为True
		if(statList[0].statDist != 0){
			flag = false;
		}
		while(currDist < distance){
			if(currStat < statList.size() - 1){
				double dist = statList[currStat + 1].statDist - statList[currStat].statDist;
				if(dist > maxDist){
					maxArrive = currDist + maxDist;
					flag = false;
					break;
				}
			}
			//如果下一个加油站油比本加油站便宜，加上能到下一个加油站的油就好
			if(currStat < statList.size() - 1
				&& statList[currStat + 1].gasPrice <= statList[currStat].gasPrice){
				double dist = statList[currStat + 1].statDist - statList[currStat].statDist;
				double remainOil = dist / distPerOil - currTankSize;
				if(remainOil > 0){ //当前油量不足
					price += remainOil * statList[currStat].gasPrice;
					currTankSize = 0.0;
				}else{ //当前油量充足，能去下一个加油站，不加油
					currTankSize -= dist / distPerOil;
				}
				currDist += dist;
				currStat++;
			}else{
				if(currStat == statList.size() - 1){ //最后一个油站
					double remainDist = distance - currDist;
					if(remainDist > maxDist){
						maxArrive = currDist + maxDist;
						flag = false;
						break;
					}
					double remainOil = remainDist / distPerOil - currTankSize;
					if(remainOil > 0){ //当前油箱中的油不足以去目的地
						price += remainOil * statList[currStat].gasPrice;
					}
					currDist = distance;
				}
				//找到满箱油路程中比本油站价格低的油站，加上能到这油站的油
				//如果没找到，判断是否能到目的地，如果能，加到达目的地的油，如果不能，加满箱油
				else{
					double available = statList[currStat].statDist + maxDist;
					int next = currStat + 1, min_stat = currStat;
					double minPrice = statList[currStat].gasPrice;
					bool flag1 = true;//没找到价格更低的油站为True
					while(next != statList.size() 
						&& statList[next].statDist <= available){ //找到下一个最便宜的油站
						if(statList[next].gasPrice < minPrice){
							minPrice = statList[next].gasPrice;
							min_stat = next;
							flag1 = false;
							break;
						}
						next++;
					}
					if(flag1){ //没找到价格更低的油站
						if(distance - currDist > maxDist){ //加满的情况
							price += (tankSize - currTankSize) * statList[currStat].gasPrice;
							Station next = statList[currStat + 1];
							currDist = next.statDist;
							currTankSize = tankSize - (currDist - statList[currStat].statDist) / distPerOil;
						}else{
							double oilSize = currTankSize - (distance - currDist) / distPerOil;
							if(oilSize < 0){ 
								price += oilSize * (-1) * statList[currStat].gasPrice;
							}
							currDist = distance;
						}
						currStat++;
					}else{
						double dist = statList[min_stat].statDist - statList[currStat].statDist;
						double remainOil = dist / distPerOil - currTankSize;
						//当前油箱中的油不足以去该油站
						if(remainOil > 0){
							price += remainOil * statList[currStat].gasPrice;
							currTankSize = 0.0;
						}else{
							currTankSize -= dist / distPerOil;
						}
						currDist += dist;
						currStat = min_stat;
					}
				}
			}
		}
		if(flag){
			cout << fixed << setprecision(2) << price << endl;
		}else{
			cout << "The maximum travel distance = " << fixed << setprecision(2) << maxArrive << endl;
		}
		statList.clear();
	}
	return 0;
}

附注：

（1）给出的测试样例中，

50 1300 12 8
7.10 0           7.10 * (150 / 12) = 88.75
7.00 150       7.00 * (300 - 150) /12 = 87.5
7.20 200
6.85 300       6.85 * 50 = 342.5
7.50 400
7.00 600       用掉了(600 - 300) / 12 = 25,剩余50 - 25 = 25,加满:7.00 * 25 = 175
7.30 1000     加多50公里路程的油, 7.30 * 50 / 12 = 30.42
6.00 1250     加多50公里路程的油, 6.00 * 50 / 12 = 25

88.75 + 87.5 + 342.5 + 175 + 30.42 + 25 = 749.17

参考文献：

[1]Thomas.H.Cormen Charles E. Leiseron、Ronald L. Rivest Clifford Srein. 算法导论（第3版）. [M]北京：机械工业出版社，2013.01；
[2]杨泽邦、赵霖. 计算机考研——机试指南（第2版）. [M]北京：电子工业出版社，2019.11；