完成N公里行程所需的加注次数-yiteyi-C++库

给定一个数字N，它表示一辆汽车在一条道路上行驶的总距离（以公里为单位）。每个1公里（1、2、3、…N）处有N个汽油泵。汽车油箱的容量是这样的：油箱加满后，它可以行驶到公里的距离。汽车必须在M个油箱处强制停车，这些油箱与起始位置的距离以M整数表示。这项任务是找出汽车必须加油的次数，包括完成N公里行程的强制停车次数。 例如：

null

输入： N=5，K=2，M=1 arr[]={3} 输出： 2. 汽车从0开始，油箱装满，行驶2公里，然后在2公里处重新加注油箱。如果再次加满油箱，汽车将在3点强制停车。它还要行驶2公里才能到达5公里的目的地。 输入： N=10，K=2，M=3 arr[]={6,7,8} 输出： 5. 汽车从0开始，在2、4停止加油，然后在6、7、8强制停车。从8公里到2公里，完成10公里的旅程。

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

方法：由于总行程为N公里，所以请在一个变量中记录到目前为止所覆盖的距离，例如 膨胀的 ，将由0初始化。定期的加薪 膨胀的 以公里计 膨胀的 小于N，因为K是自上次加注后车辆可以行驶的距离。此外，每增加一次，检查是否有强制的汽油泵停止 膨胀的 和 膨胀的 +K，如果是，那么 膨胀的 将是K加上最后一个必须停在中间的汽油泵 膨胀的 和 膨胀的 +K.此外，继续计算到达N km目的地所需的加油次数。以下是上述方法的实施情况：

C++

                         // CPP program for finding the total                       
                         // number of stops for refilling to                       
                         // reach destination of N km                       
                         #include <iostream>                       
                         using                                     namespace                                     std;                       
           
                         // Function that returns the total number of                       
                         // refills made to reach the destination of N km                       
                         int                                     countRefill(                                     int                                     N,                                     int                                     K,                                     int                                     M,                                     int                                     compulsory[])                       
                         {                       
                                                 int                                     count = 0;                       
                                                 int                                     i = 0;                       
                                                 int                                     distCovered = 0;                       
           
                                                 // While we complete the whole journey.                       
                                                 while                                     (distCovered < N) {                       
                                                 // If must visited petrol pump lie                       
                                                 // between distCovered and distCovered+K.                       
                                                 if                                     (i < M && compulsory[i] <= (distCovered + K)) {                       
                                                 // make last mustVisited as distCovered                       
                                                 distCovered = compulsory[i];                       
           
                                                 // increment the index of compulsory visited.                       
                                                 i++;                       
                                                 }                       
           
                                                 // if no such must visited pump is                       
                                                 // there then increment distCovered by K.                       
                                                 else                       
                                                 distCovered += K;                       
           
                                                 // Counting the number of refill.                       
                                                 if                                     (distCovered < N)                       
                                                 count++;                       
                                                 }                       
           
                                                 return                                     count;                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 int                                     N = 10;                       
                                                 int                                     K = 2;                       
                                                 int                                     M = 3;                       
                                                 // compulsory petrol pumps to refill at                       
                                                 int                                     compulsory[] = { 6, 7, 8 };                       
           
                                                 // function call that returns the answer to the problem                       
                                                 cout << countRefill(N, K, M, compulsory) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program for finding the                       
                         // total number of stops for                       
                         // refilling to reach                       
                         // destination of N km                       
                         import                                     java.io.*;                       
           
                         class                                     GFG                       
                         {                       
                                   
                         ;                       
           
                         // Function that returns the                       
                         // total number of refills made                       
                         // to reach the destination of N km                       
                         static                                     int                                     countRefill(                                     int                                     N,                                     int                                     K,                       
                                                 int                                     M,                                     int                                     compulsory[])                       
                         {                       
                                                 int                                     count =                                     0                                     ;                       
                                                 int                                     i =                                     0                                     ;                       
                                                 int                                     distCovered =                                     0                                     ;                       
           
                                                 // While we complete                       
                                                 // the whole journey.                       
                                                 while                                     (distCovered < N)                       
                                                 {                       
                                                 // If must visited petrol pump lie                       
                                                 // between distCovered and distCovered+K.                       
                                                 if                                     (i < M && compulsory[i] <=                       
                                                 (distCovered + K))                       
                                                 {                       
                                                 // make last mustVisited                       
                                                 // as distCovered                       
                                                 distCovered = compulsory[i];                       
           
                                                 // increment the index                       
                                                 // of compulsory visited.                       
                                                 i++;                       
                                                 }                       
           
                                                 // if no such must visited                       
                                                 // pump is there then                       
                                                 // increment distCovered by K.                       
                                                 else                       
                                                 distCovered += K;                       
           
                                                 // Counting the number of refill.                       
                                                 if                                     (distCovered < N)                       
                                                 count++;                       
                                                 }                       
           
                                                 return                                     count;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main (String[] args)                       
                         {                       
                                                 int                                     N =                                     10                                     ;                       
                                                 int                                     K =                                     2                                     ;                       
                                                 int                                     M =                                     3                                     ;                       
                                                 // compulsory petrol                       
                                                 // pumps to refill at                       
                                                 int                                     compulsory[] = {                                     6                                     ,                                     7                                     ,                                     8                                     };                       
                                   
                                                 // function call that returns                       
                                                 // the answer to the problem                       
                                                 System.out.println(countRefill(N, K,                       
                                                 M, compulsory));                       
                         }                       
                         }                       
           
                         // This code is contributed by anuj_67.                       

Python3

                         # Python 3 program for finding the total                       
                         # number of stops for refilling to reach                       
                         # destination of N km                       
           
                         # Function that returns the total number of                       
                         # refills made to reach the destination of N km                       
                         def                                     countRefill(N, K, M, compulsory):                       
                                                 count                                     =                                     0                       
                                                 i                                     =                                     0                       
                                                 distCovered                                     =                                     0                       
           
                                                 # While we complete the whole journey.                       
                                                 while                                     (distCovered < N):                       
                                   
                                                 # If must visited petrol pump lie                       
                                                 # between distCovered and distCovered+K.                       
                                                 if                                     (i < M                                     and                                     compulsory[i] <                                     =                                     (distCovered                                     +                                     K)):                       
                                   
                                                 # make last mustVisited as distCovered                       
                                                 distCovered                                     =                                     compulsory[i]                       
           
                                                 # increment the index of                       
                                                 # compulsory visited.                       
                                                 i                                     +                                     =                                     1                       
           
                                                 # if no such must visited pump is                       
                                                 # there then increment distCovered by K.                       
                                                 else                                     :                       
                                                 distCovered                                     +                                     =                                     K                       
           
                                                 # Counting the number of refill.                       
                                                 if                                     (distCovered < N):                       
                                                 count                                     +                                     =                                     1                       
           
                                                 return                                     count                       
           
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                                 N                                     =                                     10                       
                                                 K                                     =                                     2                       
                                                 M                                     =                                     3                       
                                   
                                                 # compulsory petrol pumps to refill at                       
                                                 compulsory                                     =                                     [                                     6                                     ,                                     7                                     ,                                     8                                     ]                       
           
                                                 # function call that returns the                       
                                                 # answer to the problem                       
                                                 print                                     (countRefill(N, K, M, compulsory))                       
                                   
                         # This code is contributed by                       
                         # Sanjit_Prasad                       

C#

                         // C# program for finding the                       
                         // total number of stops for                       
                         // refilling to reach                       
                         // destination of N km                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                                   
                         // Function that returns                       
                         // the total number of                       
                         // refills made to reach                       
                         // the destination of N km                       
                         static                                     int                                     countRefill(                                     int                                     N,                                     int                                     K,                       
                                                 int                                     M,                                     int                                     []compulsory)                       
                         {                       
                                                 int                                     count = 0;                       
                                                 int                                     i = 0;                       
                                                 int                                     distCovered = 0;                       
           
                                                 // While we complete                       
                                                 // the whole journey.                       
                                                 while                                     (distCovered < N)                       
                                                 {                       
                                                 // If must visited petrol pump                       
                                                 // lie between distCovered and                       
                                                 // distCovered+K.                       
                                                 if                                     (i < M && compulsory[i] <=                       
                                                 (distCovered + K))                       
                                                 {                       
                                                 // make last mustVisited                       
                                                 // as distCovered                       
                                                 distCovered = compulsory[i];                       
           
                                                 // increment the index                       
                                                 // of compulsory visited.                       
                                                 i++;                       
                                                 }                       
           
                                                 // if no such must visited                       
                                                 // pump is there then                       
                                                 // increment distCovered by K.                       
                                                 else                       
                                                 distCovered += K;                       
           
                                                 // Counting the number of refill.                       
                                                 if                                     (distCovered < N)                       
                                                 count++;                       
                                                 }                       
           
                                                 return                                     count;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     Main ()                       
                         {                       
                                                 int                                     N = 10;                       
                                                 int                                     K = 2;                       
                                                 int                                     M = 3;                       
                                   
                                                 // compulsory petrol                       
                                                 // pumps to refill at                       
                                                 int                                     []compulsory = {6, 7, 8};                       
                                   
                                                 // function call that returns                       
                                                 // the answer to the problem                       
                                                 Console.WriteLine(countRefill(N, K,                       
                                                 M, compulsory));                       
                         }                       
                         }                       
           
                         // This code is contributed by anuj_67.                       

PHP

                         <?php                       
                         // PHP program for finding the total                       
                         // number of stops for refilling to                       
                         // reach destination of N km                       
           
                         // Function that returns the total                       
                         // number of refills made to reach                       
                         // the destination of N km                       
                         function                                     countRefill(                                     $N                                     ,                                     $K                                     ,                                     $M                                     ,                       
                                                 $compulsory                                     )                       
                         {                       
                                                 $count                                     = 0;                       
                                                 $i                                     = 0;                       
                                                 $distCovered                                     = 0;                       
           
                                                 // While we complete                       
                                                 // the whole journey.                       
                                                 while                                     (                                     $distCovered                                     <                                     $N                                     )                       
                                                 {                       
                                                 // If must visited petrol                       
                                                 // pump lie between distCovered                       
                                                 // and distCovered + K.                       
                                                 if                                     (                                     $i                                     <                                     $M                                     and                                     $compulsory                                     [                                     $i                                     ] <=                       
                                                 (                                     $distCovered                                     +                                     $K                                     ))                       
                                                 {                       
                                                 // make last mustVisited                       
                                                 // as distCovered                       
                                                 $distCovered                                     =                                     $compulsory                                     [                                     $i                                     ];                       
           
                                                 // increment the index                       
                                                 // of compulsory visited.                       
                                                 $i                                     ++;                       
                                                 }                       
           
                                                 // if no such must visited                       
                                                 // pump is there then                       
                                                 // increment distCovered by K.                       
                                                 else                       
                                                 $distCovered                                     +=                                     $K                                     ;                       
           
                                                 // Counting the number                       
                                                 // of refill.                       
                                                 if                                     (                                     $distCovered                                     <                                     $N                                     )                       
                                                 $count                                     ++;                       
                                                 }                       
           
                                                 return                                     $count                                     ;                       
                         }                       
           
                         // Driver Code                       
                         $N                                     = 10;                       
                         $K                                     = 2;                       
                         $M                                     = 3;                       
           
                         // compulsory petrol                       
                         // pumps to refill at                       
                         $compulsory                                     =                                     array                                     (6, 7, 8);                       
           
                         // function call that returns                       
                         // the answer to the problem                       
                         echo                                     countRefill(                                     $N                                     ,                                     $K                                     ,                                     $M                                     ,                       
                                                 $compulsory                                     ) ,                                     ""                                     ;                       
           
                         // This code is contributed by anuj_67.                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript program for finding the total                       
                         // number of stops for refilling to                       
                         // reach destination of N km                       
           
                         // Function that returns the total number of                       
                         // refills made to reach the destination of N km                       
                         function                                     countRefill(N, K, M, compulsory)                       
                         {                       
                                                 var                                     count = 0;                       
                                                 var                                     i = 0;                       
                                                 var                                     distCovered = 0;                       
           
                                                 // While we complete the whole journey.                       
                                                 while                                     (distCovered < N) {                       
                                                 // If must visited petrol pump lie                       
                                                 // between distCovered and distCovered+K.                       
                                                 if                                     (i < M && compulsory[i] <= (distCovered + K))                       
                                                 {                       
                                                 // make last mustVisited as distCovered                       
                                                 distCovered = compulsory[i];                       
           
                                                 // increment the index of compulsory visited.                       
                                                 i++;                       
                                                 }                       
           
                                                 // if no such must visited pump is                       
                                                 // there then increment distCovered by K.                       
                                                 else                       
                                                 distCovered += K;                       
           
                                                 // Counting the number of refill.                       
                                                 if                                     (distCovered < N)                       
                                                 count++;                       
                                                 }                       
           
                                                 return                                     count;                       
                         }                       
           
                         // Driver Code                       
                         var                                     N = 10;                       
                         var                                     K = 2;                       
                         var                                     M = 3;                       
           
                         // compulsory petrol pumps to refill at                       
                         var                                     compulsory = [ 6, 7, 8 ];                       
           
                         // function call that returns the answer to the problem                       
                         document.write( countRefill(N, K, M, compulsory));                       
           
                         </script>                       

输出：

时间复杂性 ：O（N） 辅助空间 ：O（1）

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章