poj2431 priority team greedy

A group of cows grabbed a truck and ventured into an expedition deep in the jungle. As a rather poor driver, unfortunately, the cow managed to run over a rock and pierce the truck's fuel tank. Trucks now leak one fuel unit per unit of distance they run.

In order to repair the truck, the cow needs to drive along a long winding road to the nearest town (no more than 1000000 units). On this road, between the current location of the town and the truck, there are N (1 < = N < = 10000) fuel stations, and cows can stop to get additional fuel (1... 100 units per station).

The jungle is a dangerous place for humans, especially for cows. Therefore, the cow hopes to stop fuel as little as possible on the way to town. Fortunately, the tank capacity on their truck is very large. In fact, there is 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 < = 1000000).

Determine the minimum number of stops required to reach the town, or the cow cannot reach the town at all.

Idea 1: priority queue
In other words, STL is really easy to use. This problem doesn't need priority queue. I haven't thought of it for a long time
1. Default operator<

priority_queue<int> q;  

2. Define a functor greater < >, which can be used to declare the small top heap (non descending order) for basic types

 priority_queue<int, vector<int>, greater<int> > q;

3. For user-defined types,
Overload operator 1.3<

		priority_queue<Node> q;  
		bool operator<( Node a, Node b ){//Ascending order 
		    if( a.x== b.x ) return a.y> b.y;
		    	return a.x> b.x; 

3.2 custom cmp

	 priority_queue<Node, vector<Node>, cmp> q;    
	 bool cmp(node a, node b){
 		if( a.x== b.x ) return a.y> b.y;
		   return a.x> b.x;

2. Specific ideas
See note
Code of this question:

using namespace std;
#define LL long long

struct node{
    int l, p; //l is the distance and p is the oil quantity
    bool operator < (const node &a){ //Overloaded operator to end of descending sort
        return l > a.l;

priority_queue<int> q;
int N, L, P;
int main(){
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> p[i].l >> p[i].p;
    sort(p, p+N); //Sort in descending order to the end point  
    cin >> L >> P;
    q.push(P); //push the initial fuel volume into the queue
    int ans = 0, i = 0; //ans records the results and i records the gas stations that joined the queue
    while(L > 0 && !q.empty()){ 
        ans++; L -= q.top(); q.pop(); //Indicates that the refueling distance is reduced and the current largest gas station is used
        while(L <= p[i].l && i < N){ //It means passing the gas station,
            q.push(p[i].p); i++;  //Join the queue in ascending order of fuel volume

    if(L > 0) cout << -1 << endl;
    else cout << ans-1 << endl;
    return 0; 

2: Greedy thinking:

Posted by tabs on Thu, 19 May 2022 07:27:06 +0300