大一新生贪心算法的记录学习，欢迎大家一起讨论~

贪心思想：

1. 铺设道路，积木大赛

[www.luogu.com.cn/problem/P50…]

[www.luogu.com.cn/record/2064…]

分析：

两题贪心思想相同，放在一起。

猜想：结果为初始高度a[0]加上在a[i] >a[i-1]的前提下的（a[i]-a[i-1])的加和

a0+∑i=1i=n−1(a[i]−a[i−1])a_0 + \sum_{i=1}^{i=n-1}(a[i] - a[i-1])

证明：每个区域的深度形成的层数可以通过分层的方式处理。每个递增的部分需要额外的天数来处理，而无法与之前的一并处理。而其他情况下，这些层可以被前面的处理覆盖，不需要额外的天数。因此，总天数等于各个递增差值的总和。

c++
 代码解读
复制代码
#include 
#include 

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> d(n);
    for (int i = 0; i < n; ++i) {
        cin >> d[i];
    }
    
    int total_days = d[0];
    for (int i = 1; i < n; ++i) {
        if (d[i] > d[i - 1]) {
            total_days += d[i] - d[i - 1];
        }
    }
    
    cout << total_days << endl;
    return 0;
}

2.无重叠区间，用最少数量箭引爆气球

[435. 无重叠区间 - 力扣（LeetCode）]

[用最少数量的箭引爆气球 - 提交记录 - 力扣（LeetCode）]

分析：

两题问题相似：一个是问无重叠区间，一个是问重叠区间，索性放在一起分析了。
以气球分析举例：
一箭能射爆几个气球由交区间得到，不妨随意射一箭，移动箭，使之尽可能多的擦气球，连续射爆气球需把相似的尽可能放在一起，故一定是要排序的。
使用左端点排序如何? 若一个气球区间足够长，左端点较小，则无法判断其余气球情况。
故最好的排序是对右端点进行排序，不会出现以上异常状况，我们假想第一箭射在第一区间末尾，若射不到下一个气球则更新一箭，这一箭射在这一气球的末尾。
注意初始的right开小，以达到成功更新区间的目的。

c++
 代码解读
复制代码
// 题目的反面为 最长不相交的区间个数
class Solution {
public:
    int eraseOverlapIntervals(vectorint>>& intervals) {
        //按右端点进行排序
        sort(intervals.begin(),intervals.end(),
            [](auto &a, auto &b){
                return a[1] < b[1];
            });
        int ans = 0;
        int right = -1e5;
        for(auto&interval:intervals){
            //得到一可连续区间
            if(interval[0] >= right) {
                right = interval[1];
                ans ++;
            }
        }
        return intervals.size() - ans;
    }
};

c++
 代码解读
复制代码
class Solution {
public:
    int findMinArrowShots(vectorint>>& points) {
        if(points.empty()) return 0;
        sort(points.begin(),points.end(),
            [](auto& a,auto& b){
                return a[1] < b[1];
            });
        int ans = 0;
        long long right = LLONG_MIN;
        for(auto& point:points){
            if(right < point[0]){
                right = point[1];
                ans++; //多射一箭 
            }
        }
        // 没有相交的区间
        if(ans == 0) ans = points.size();
        return ans;
    }
};

3.合并K个升序链表

[leetcode.cn/problems/me…]

分析：

温习下结构体下的链表

c++
 代码解读
复制代码
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

想得到从小到大排列的链表，而已知条件为不同组内部已排好大小的链表。
形象的比喻说是，得到全校同学按身高从低到高站队，而每个班已经按顺序排好，就是如何合并的问题。
思考 先从各个班里找到各班最低的同学，最低中在挑选最低，次低等等。如何实现快速找到符合要求的同学?
考虑到优先队列，可实现top为队列中的最小值，依次往下寻找。
总结：贪心与优先队列，之于火腿肠与泡面，最佳伴侣，达成需求。

c++
 代码解读
复制代码
class Solution {
public:
    ListNode* mergeKLists(vector& lists) {
        // 使用虚拟头节点简化链表操作
        // using node = ListNode可以减轻代码量，节约时间
        ListNode* dummy = new ListNode();
        ListNode* tail = dummy; // 尾指针用于构建结果链表

        // 自定义比较函数，构建最小堆：当a的值大于b时，a应排在后面（堆顶为最小元素）
        auto cmp = [](ListNode* a, ListNode* b) { 
        	return a->val > b->val; 
        };
        // 初始化优先队列，存储各链表当前节点
        priority_queue, decltype(cmp)> pq(cmp);

        // 将所有非空链表的头节点加入优先队列
        for (auto& list : lists) {
            if (list) {
                pq.push(list);
            }
        }

        // 处理优先队列中的节点
        while (!pq.empty()) {
            ListNode* current = pq.top(); // 取出当前最小节点
            pq.pop();
            
            // 将当前节点连接到结果链表尾部
            tail->next = current;
            // 尾部向后推移
            tail = tail->next;

            // 如果当前节点有后续节点，将其加入优先队列
            if (current->next) {
                pq.push(current->next);
            }
        }

        return dummy->next; // 返回合并后的链表头节点
    }
};

4.回文数组（lq19715)

[www.lanqiao.cn/problems/19…]

分析：

定义一数组记录对称元素的差距diff，记diff[i] = a[i] - a[n-i+1]
策略一：相邻元素同加同减
策略二：单一元素加或单一元素减
贪心的想操作步骤一定是优先策略一，无法使用时再使用策略二。
这是显然符合直觉的，简单证明： 若某两个元素采用n次策略一，操作次数为n；而策略二，操作次数为2n。
何种情况采用策略一呢？diff[i] 需要与 diff[i+1] 同号，若异号则会使代价增大。
操作过后，剩余元素全部采取策略二
据此逻辑编写代码。

c++
 代码解读
复制代码
#include 
using namespace std;
int main()
{
  // 请在此输入您的代码
  int n;
  cin>>n;
  vector<int> a(n+1),diff(n+1);
  for(int i = 1; i <= n; i++) cin>>a[i];
  for(int i = 1; i <= n/2; i++){
    diff[i] = a[i] - a[n-i+1];
  }
  n /= 2;
  long long ans = 0;
  for(int i = 1; i <= n; i++){
    if(i+1 <= n){
      //同号，先采用策略二
      if(1ll * diff[i] * diff[i+1] > 0){//使用1ll 防止相乘溢出
        int min_abs = min(abs(diff[i]), abs(diff[i+1]));
        ans += min_abs;
        if(diff[i] > 0){
          diff[i] -= min_abs;
          diff[i+1] -= min_abs;
        }
        else{
          diff[i] += min_abs;
          diff[i+1] += min_abs;
        }
      }
    }
    ans += abs(diff[i]);
  }
  cout<
  return 0;
}

5.做作业（hdoj1789)

[acm.hdu.edu.cn/showproblem…]

分析:

我们得到相应的两组数据，截止日期和完成收益。
如果按照截止日期排序，会导致收益高的反而被占用；按照完成收益去排序，会导致最后可能没活可干，收益不能最大化。
那我们不妨换个角度去想，以最后一天去向前遍历，每次找到以每一天为期限的性价比最高的去完成，采取逆向思维。这是可行的，因为任务可以在期限前做完，从后往前遍历就是能充分利用高性价比任务。
每次都要找到某一天的最高性价比任务，自然而然的想到贪心的好搭档—优先队列，以logn的复杂度找到元素。

c++
 代码解读
复制代码
#include 
using namespace std;
int main(){
    int t;
    cin >> t;
    while(t--){
      //记录最大日期
      int n, maxd = 0, total = 0;
      cin >> n;
      vectorint,int>> arr(n);
      for(int i = 0;i < n;i++){
        cin>>arr[i].first;
        maxd = max(maxd,arr[i].first);
      }
      for(int i = 0;i < n;i++){
        cin>>arr[i].second;
        total += arr[i].second;
      }
      // 记录maxd天内各个截止日期的任务情况。
      vectorint>> scores(maxd+1);
      for(int i = 0;i < n;i++){
        scores[arr[i].first].push_back(arr[i].second);
      }
      // 在每一日内每次一定是优先找扣分多的情况，想到优先队列。
      priority_queue<int> pq;
      for(int i = maxd;i >= 1;i--){
        for(auto&s:scores[i]) pq.push(s);
        if(pq.size()){
          total -= pq.top();
          pq.pop();
        }
      }
      cout<
    }
    return 0;
}

6.平均（lq3532)

[www.lanqiao.cn/problems/35…]

分析：

若去统计谁变成谁，谁又变成了谁思路会过于复杂。
事实上，我们只需要找出每个数字应出现的次数，即n/10个元素中代价最大的保持不变就好，其余相对较低的代价统统加上即可得出正确答案。
故只需要对每个数字中的代价从大到小排序即可。

c++
 代码解读
复制代码
#include 
using namespace std;
int main()
{
  int n;
  cin >> n;
  vector<int> scores[10];
  for(int i = 0;i < n;i++) {
    int a, b;
    cin >> a >> b;
    scores[a].push_back(b);
  }
  long long ans = 0;
  for(int i = 0;i < 10;i++){
    sort(scores[i].begin(),scores[i].end(),greater<int>());
    for(int j = n/10;j < scores[i].size();j++){
      ans += scores[i][j];
    }
  }
  cout<
  // 请在此输入您的代码
  return 0;
}

7.食堂（lq19724)

[www.lanqiao.cn/problems/19…]

分析：

先分析下六人桌下的坐法：
两个三人寝，一个四人寝一个两人寝，三个两人寝，一个三人寝一个两人寝（空一个座位）
3+3，4+2，2+2+2，3+2
四人桌下的坐法： 一个四人寝，两个两人寝，一个三人寝，一个两人寝
4，2+2，3，2
各种坐法如何排出优先级？想到贪心策略，一定会有性价比的优先级之分，寻求性价比高的方案。
六人桌下 一定优先安排两个三人寝，为何？
三人寝去和两人寝拼桌坐六人桌还是三人寝坐四人桌，都会导致位置的浪费，不符合最大利益，所以优先处理三人寝。
其次就是两人寝和四人寝的混合搭配等方案，这些方案都可以坐满六人桌。
如果排完先前位置，六人桌仍有空余，则便是三人寝和两人寝坐六人桌
四人桌下优先坐满，若四人桌仍有空余，便是三人寝，两人寝的坐法。
思路如此，下面开始编写代码。

c++
 代码解读
复制代码
#include 
using namespace std;
int main()
{
  int q;
  cin >> q;
  //预处理两人寝，三人寝，四人寝，所坐位置数量。
  vectorint,int,int,int>> patterns = {
    {0,2,0,6},
    {1,0,1,6},
    {3,0,0,6},
    {1,1,0,5},
    {0,0,1,4},
    {2,0,0,4},
    {0,1,0,3},
    {1,0,0,2},
  };
  while(q--){
    int a2, a3, a4, b4, b6;
    cin >> a2 >> a3 >> a4 >> b4 >> b6;
    long long ans = 0;
    //构造b6张6人桌与b4张4人桌
    vector<int> boards(b6,6);
    boards.insert(boards.end(),b4,4);
    
    //遍历桌子
    for(auto&b:boards){
      for(auto&[c2,c3,c4,sum]:patterns){
        if(a2>=c2 && a3>=c3 && a4 >= c4 && b >= sum){
          ans += sum;
          a2 -= c2;
          a3 -= c3;
          a4 -= c4;
          //找到方案，终止这张桌子的操作
          break;
        }
      }
    }
    cout<
  }
  // 请在此输入您的代码
  return 0;
}

8.三国（lq3518)

[www.lanqiao.cn/problems/35…]

分析：

获胜的条件是某国的总士兵数严格大于另外两国之和。
对于每个国家（X、Y、Z），我们需要找到最大的k，使得选择k个事件时，该国的总贡献值大于另外两国之和。即

∑i=1i=k(Ai−Bi−Ci)>0\sum{i=1}{i=k}(A_i - B_i - C_i) > 0
记di=Ai−Bi−Ci。即Si=∑i=1i=kdi>0的k达最大的解记d_i = A_i - B_i - C_i。即 S_i = \sum{i=1}{i=k}d_i > 0 的k达最大的解

则得到贪心策略：对于每个国家，将事件按对应的贡献值之差进行降序排序，计算前缀和。前缀和大于0时的事件才是符合要求的情况。
完成三个国家的贪心策略时，建议分装函数来处理，修改核心逻辑便于笔误后的修正。

c++
 代码解读
复制代码
#include 
using namespace std;
using xyz = tuple<int,int,int>;
int main()
{
  int n;
  cin >> n;
  vector arr(n);
  for(auto&[x,_,__]:arr) cin>>x;
  for(auto&[_,x,__]:arr) cin>>x;
  for(auto&[_,__,x]:arr) cin>>x;
  long long ans = -1;
  auto calc = [&](){
    auto getV = [](xyz &x){
      auto [a,b,c] = x;
      return a - b - c;
    };
    sort(arr.begin(),arr.end(),[&](xyz &prev,xyz &cur){
      return getV(prev) > getV(cur);
    });
    long long sum = 0, cnt = 0;
    for(auto&x:arr){
      sum += getV(x);
      cnt += (sum > 0);
    }
    if(cnt == 0) return;
    ans = max(ans,cnt);
  };
  calc();
  for(auto&[a,b,c]:arr) swap(a,b);
  calc();
  for(auto&[a,b,c]:arr) swap(a,c);
  calc();
  cout<
  // 请在此输入您的代码
  return 0;
}

9.最大开支（lq3541)

[www.lanqiao.cn/problems/35…]

分析：

题干很长，先来简单分析下题意，倘若同学们想让小蓝破费，消费怎么贵怎么来，倘若团购某项目会导致整体更便宜，则一定不会去或者去其他昂贵项目。问最破费情况下，小蓝需要花多少钱？
每个项目的总费用为 X * max(Ki * X + Bi, 0)，其中 X 是选择该项目的人数。我们需要最大化所有项目的总费用之和。

贪心策略：每次选择能带来最大费用增量的项目分配一个用户。维护一个优先队列，存储每个项目增加一人时的费用增量，得到每个项目价格增量以及相应的参加人数，每次取增量最大的项目。

c++
 代码解读
复制代码
#include 
using namespace std;

int main() {
  int n, m;
  cin >> n >> m;
  priority_queuelong long, int, int, int>> pq;
  for (int i = 0; i < m; i ++) {
    int k, b;
    cin >> k >> b;
    pq.emplace(b + k, k, b, 1);
  }
  long long ans = 0;
  while (n --) {
    auto [delta_price, k, b, x] = pq.top();
    pq.pop();
    if (delta_price <= 0) break;
    ans += delta_price;
    long long price = 1ll * (b + k * x) * x;
    long long next_price = 1ll * (b + k * (x + 1)) * (x + 1);
    pq.emplace(next_price - price, k, b, x + 1);
  }
  cout << ans << endl;
}

10.巧克力（lq1596）

[www.lanqiao.cn/problems/15…]

分析：

和第五题做作业一样，是典型的deadline问题。
贪心策略+优先队列：
逆向思考问题，倒序处理，从最后一天遍历到第一天，吃保质期内的最便宜巧克力。

用优先队列维护当前可用的巧克力，按价格排序。每天选择价格最低的巧克力，保证总花费最小，可以logn的复杂度查询到符合要求的最佳选择。

处理每天时，将符合保质期条件的巧克力加入队列,动态更新。使用后若仍有剩余，重新放回队列。

c++
 代码解读
复制代码
#include 
using namespace std;

int main() {
  int x, n;
  cin >> x >> n;
  vectorint, int, int>> chos(n);
  // 	(保质期d, 价格p, 数量c) 令截止日期为元组首元素，排序时就不用在撰写匿名函数的排序方法了
  for (auto &[d, p, c] : chos) cin >> p >> d >> c;
  sort(chos.begin(), chos.end()); // 按保质期升序排序

  priority_queueint, int>, vectorint, int>>, greaterint, int>>> pq;
  long long ans = 0;
  int index = n - 1; // 从最大的保质期开始遍历

  // 倒序处理每一天
  for (; x > 0; x--) {
    // 将符合当前天数要求的巧克力加入队列
    while (index >= 0) {
      auto [d, p, c] = chos[index];
      if (d >= x) {
        pq.emplace(p, c);
        index--;
      } else break;
    }
    // 若无法满足当天需求终止循环。
    if (pq.empty()) break;
    // 取出价格最低的巧克力
    auto [p, c] = pq.top();
    pq.pop();
    ans += p;
    if (c > 1) pq.emplace(p, c - 1); // 剩余放回队列
  }
  //x若不为0，则发生提前退出，无可用方案。
  cout << (x == 0 ? ans : -1) << endl;
}

11.打折（lq2213）

[www.lanqiao.cn/problems/22…]

分析：

将每个店铺的折扣活动拆分为两个事件（开始和结束），按时间排序后处理。
如何实时维护当前最低价呢？
我们想到multiset，排列进去的元素有顺序，且可重复。
利用multiset动态维护每个物品的可用价格，实现快速获取最小值。
记初始总价为所有物品最低价之和，遍历事件时调整价格并更新最小总价。

c++
 代码解读
复制代码
#include 
using namespace std;

int main() {
  int n, m;
  cin >> n >> m;
  vectorint, int, int, int>> actions;
  vectorint>> prices(n + 1);
  for (int i = 0; i < m; i++) {
    int start, end, discount, cnt;
    cin >> start >> end >> discount >> cnt;
    while (cnt --) {
      int type, basePrice;
      cin >> type >> basePrice;
      prices[type].insert(basePrice); // 原价加入集合
      // 生成折扣开始和结束事件
      actions.emplace_back(start, discount, type, basePrice);
      actions.emplace_back(end + 1, -discount, type, basePrice);
    }
  }
  sort(actions.begin(), actions.end());
  long long total = 0;
  for (int i = 1; i <= n; i ++) {
    total += *prices[i].begin(); // 初始总价为原价最低价之和
  }
  long long ans = total;
  for (auto [time, discount, type, basePrice] : actions) {
    int currentPrice = *prices[type].begin();
    if (discount > 0) { // 折扣生效，插入折扣价
        prices[type].insert(1LL * basePrice * discount / 100);
    } else { // 折扣结束，移除对应的折扣价
        prices[type].erase(prices[type].find(1LL * basePrice * (-discount) / 100));
    }
    int price = *prices[type].begin(); // 当前最低价
    total += (price - currentPrice); // 更新总价变化
    ans = min(ans, total); // 记录最小总价
  }
  cout << ans << endl;
}
注：本文转载自juejin.cn的Nqg111的文章"https://juejin.cn/post/7479343249364615204"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！