POJ2431 優先佇列+貪心 - biaobiao88-有解無憂

以下代碼可對結構體陣列中的元素進行排序，也差不多算是一個小小的模板了吧

#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
	int x;
	int y;
	bool operator<(const node &a) const//此操作是對運算子"<"進行重構 
	{
		return x < a.x;//對結構體陣列x進行從大到小排序 
//		return y > a.y;//對結構體陣列y進行從大到小排序 
	}
}s[100];

//bool cmp(int x,int y)//這個重構函式不能用在結構體陣列中 
//{
//	return x > y;
//}

int main()
{
	int n;
	cin >> n;
	for(int i = 0;i < n;i++)
		cin >> s[i].x >> s[i].y;
	
	sort(s,s+n);
	for(int i = 0;i < n;i++)
		cout << s[i].x << " " << s[i].y << endl;
	cout << endl;
	return 0;
}

運行結果：

也可以這樣

#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
    int x;
    int y;
    bool operator<(const node &a) const 
    {
        return x > a.x; 
    }
}s[100];

bool cmp(node m,node n)
{
    m.x < n.x;
}

int main()
{
    int n;
    cin >> n;
    for(int i = 0;i < n;i++)
        cin >> s[i].x >> s[i].y;
    
    sort(s,s+n);
    for(int i = 0;i < n;i++)
        cout << s[i].x << " " << s[i].y << endl;
    cout << endl;
    return 0;
}

對優先佇列的應用，POJ2431是一個很好的題目，此題用了優先佇列+貪心

Expedition

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 29720		Accepted: 8212

Description

A group of cows grabbed a truck and ventured on an expedition deep into the jungle. Being rather poor drivers, the cows unfortunately managed to run over a rock and puncture the truck's fuel tank. The truck now leaks one unit of fuel every unit of distance it travels.

To repair the truck, the cows need to drive to the nearest town (no more than 1,000,000 units distant) down a long, winding road. On this road, between the town and the current location of the truck, there are N (1 <= N <= 10,000) fuel stops where the cows can stop to acquire additional fuel (1..100 units at each stop).

The jungle is a dangerous place for humans and is especially dangerous for cows. Therefore, the cows want to make the minimum possible number of stops for fuel on the way to the town. Fortunately, the capacity of the fuel tank on their truck is so large that there is effectively no limit to the amount of fuel it can hold. The truck is currently L units away from the town and has P units of fuel (1 <= P <= 1,000,000).

Determine the minimum number of stops needed to reach the town, or if the cows cannot reach the town at all.

Input

* Line 1: A single integer, N

* Lines 2..N+1: Each line contains two space-separated integers describing a fuel stop: The first integer is the distance from the town to the stop; the second is the amount of fuel available at that stop.

* Line N+2: Two space-separated integers, L and P

Output

* Line 1: A single integer giving the minimum number of fuel stops necessary to reach the town. If it is not possible to reach the town, output -1.

Sample Input

Sample Output

Hint

INPUT DETAILS:

The truck is 25 units away from the town; the truck has 10 units of fuel. Along the road, there are 4 fuel stops at distances 4, 5, 11, and 15 from the town (so these are initially at distances 21, 20, 14, and 10 from the truck). These fuel stops can supply up to 4, 2, 5, and 10 units of fuel, respectively.

OUTPUT DETAILS:

Drive 10 units, stop to acquire 10 more units of fuel, drive 4 more units, stop to acquire 5 more units of fuel, then drive to the town.

Source

USACO 2005 U S Open Gold 思路：貪心思路為，在假設汽車一路向前，在途中有經過加油站的話，把加油站進行排序，符合條件的加油站中的汽油從大到小排序，存到優先佇列中，在汽車用完時，即隨時可以在佇列的隊頭取汽油，使得汽車盡可能加最多的汽油，停最少次

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
struct node
{
    int dis;
    int fuel;
    bool operator<(const node &a) const//此重構操作，請參考上面的代碼 
    {
        return dis > a.dis;//回傳dis，說明是對dis這個陣列進行排序操作 
    }
}stop[10005];

priority_queue<int> que;

int main()
{
    int n,l,p;
    cin >> n;
    for(int i = 0;i < n;i++)
        cin >> stop[i].dis >> stop[i].fuel;
    cin >> l >> p;
    int ans = 0;
    sort(stop,stop + n);//對加油站距離dis陣列進行從大到小排序 
    que.push(p);//佇列自動從大到小排序，即排序汽油p 
    int temp = 0;
    while(l > 0 && !que.empty())//卡車未到達終點并且卡車在當前汽油用完前有路過加油站 
    {
        ans++;//卡車停下加一次油計數器 
        l -= que.top();//加油，更新一次汽油用盡后距離終點的距離 
        que.pop();//洗掉已用的加油站的汽油 
        while(l <= stop[temp].dis && temp < n)//卡車距離終點的距離小于等于最近加油站的距離并且這個加油站的位置在終點加油站前面，這里假設終點也為一個加油站，//l <= stop[i].dis意思是卡車能經過離它最近的一個加油站，如果大于的話，說明卡車停下時沒有加油站可加油  
            que.push(stop[temp++].fuel);//將經過的加油站壓入優先佇列,要使用的時候就取隊頭元素（隊頭中存的汽油最大） //如果經過加油站，則一定要將該加油站的可加油量添加到優先佇列當中 
    }//temp++說明離卡車最近的加油站，卡車繼續往前開，加油站點也依次往后，所以變數temp需要自增
    if(l > 0)//如果卡車距離終點的距離還大于0的話，即通過不了終點 
        cout << "-1" << endl;
    else
        cout << ans - 1 << endl;//在起點深度時候記為一次加油，這里需要減去1 
    return 0;
}

其中代碼有詳細的注釋，希望注釋能加深理解

代碼參考于：博客園-小小菜鳥

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/89833.html

標籤：C++

上一篇：STL之string

下一篇：set容器與map容器的簡單應用