Meaning:
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:
#include<iostream> #include<queue> #include<stack> #include<cstring> #include<stdlib.h> #include<cstdio> #include<iostream> #include<algorithm> 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; } }p[10001]; 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; //system("pause"); return 0; }
2: Greedy thinking: