leetcode 330. 按要求补齐数组 【贪心构造】

太过爱你忘了你带给我的痛 2022-10-22 02:46 156阅读 0赞

思路参考：https://leetcode-cn.com/problems/patching-array/solution/an-yao-qiu-bu-qi-shu-zu-tan-xin-suan-fa-b4bwr/

当前集合可以覆盖[1,b]，在当前集合上增加一个数字，使得这个区间可以覆盖到的数组最多，并且保证区间没有产生空隙

  1. #define debug(x) cout<<#x<<": "<<(x)<<endl;
  3. using ll = long long;
  5. class Solution { 
  6. public:
  7.     int minPatches(vector<int>& a, int n) { 
  8.         ll r = 0;
  9.         int ret = 0;
  10.         int i = 0;
  11.         while(r < n){ 
  12.             if(i<a.size() && r+1 >= a[i]){ 
  13.                 r += a[i];
  14.                 i++;
  15.             }
  16.             else {  //r+1 < a[i])
  17.                 ret ++;
  18.                 r += (r+1);
  19.             } 
  20.         }
  22.         return ret;
  23.     }
  24. };

在这里插入图片描述

发表评论

表情：
评论列表 （有 0 条评论，156人围观）

还没有评论，来说两句吧...

相关阅读