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是一個很好的題目，此題用了優先隊列+貪心

Description

Input

Output

Sample Input

4
4 4
5 2
11 5
15 10
25 10

Sample Output

2

Hint

Source

#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;
}

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

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