7-5 car refueling problem (20 points) (idea + detailed explanation) come treasure!!!!!!!!!!!!!

One : subject

Title source : Wang Xiaodong 《 Algorithm design and analysis 》

A car can run after it is filled with oil n km . There are several gas stations on the journey . Design an effective algorithm , Point out that At which gas stations do you stop for gas , Minimize the number of refueling along the way .

Input format :
The first line has 2 A positive integer n and k(k<=1000 ), It means that the car can run after filling up with oil n km , And there are k A gas station . The second line has k+1 It's an integer , It means the first one k A gas station and the k-1 The distance between gas stations . The first 0 A gas station indicates the place of departure , The car has been filled with gas . The first k+1 A gas station indicates the destination .

Output format :
Output minimum refueling times . If you can't get to your destination , The output “No Solution!”.

sample input :

7 7
1 2 3 4 5 1 6 6

sample output :

4

Two : Ideas

Ideas :1. Follow the maximum value of this distance with n Compare If it is larger than it, it will directly output No Solution!
2. Otherwise, each section of the journey can be passed with full fuel
3. If you can go there , So when the journey m Less than n when , Yes n updated n = n-m; Then judge the next distance
Follow n The relationship between , If m Greater than n Then come on , Count at the same time

3、 ... and : Upper code

/** Ideas :1. Follow the maximum value of this distance with n Compare If it is larger than it, it will directly output No Solution! 2. Otherwise, each section of the journey can be passed with full fuel 3. If you can go there , So when the journey m Less than n when , Yes n updated n = n-m; Then judge the next distance Follow n The relationship between , If m Greater than n Then come on , Count at the same time */
#include<bits/stdc++.h>
using namespace std;
int n,k;
int res(vector<int>& v,int val){

int maxx = 0,cnt = 0;
for(int i = 0; i < v.size(); i++){

maxx = max(maxx,v[i]);
}
if(maxx > n){

return -1;
}
for(int i = 0; i < v.size(); i++){

if(n >= v[i]){

n = n - v[i];
}else{

n = val;
n = n - v[i];
cnt++;
//cout << n << ' ';
}
// cout << v[i] << ' ';
}
return cnt;
}
int main(){

vector<int>v;
cin >> n >> k;
for(int i = 0; i < k+1; i++){

int num;
cin >> num;
v.push_back(num);
}
int temp = res(v,n);
if(temp == -1){

cout << "No Solution!";
}else{

// cout << endl;
cout << temp;
}
}

 Insert picture description here
Another nag Remember to refuel treasure !!!!!!!!!!!!!!!!

Please bring the original link to reprint ,thank
Similar articles

2021-11-25

2021-11-25

2021-11-25