贪心，蓝桥杯真题 [巧克力]

本文主要是介绍贪心，蓝桥杯真题 [巧克力]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

2.巧克力 - 蓝桥云课 (lanqiao.cn)

---

二、解题报告

1、思路分析

做法：我们将巧克力按照价格升序排序，然后顺序枚举巧克力wi，查找小于等于bi的日期中最大的未被选择日期，将当前巧克力分配给该日期

证明正确性：

假如存在最优解和贪心策略不一致，则一定存在wi 分配给 第 x天，wj分配给第y天

满足：x < y <= bi，显然wj也可以满足第x天，那么二者交换，并不会使得解更差

我们调整所有逆序对不会使得解更差，故贪心策略成立

2、复杂度

时间复杂度： O(nlogm)空间复杂度：O(n)

3、代码详解

​

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
#define int long long
const int N = 1e5 + 10; 
int n, m, s;
set<int> st; 
struct node{int a, b, c;bool operator<(const node& x) const{return a < x.a;} 
}nodes[N];
signed main(){cin >> m >> n;for(int i = 0, a, b, c; i < n; i ++){cin >> a >> b >> c;nodes[i] = { a, b, c };}sort(nodes, nodes + n);for(int i = 1; i <= m; i ++) st.insert(i);for(int i = 0; st.size() && i < n; i ++) {auto it = st.upper_bound(nodes[i].b);	while(nodes[i].c && st.size() && it != st.begin()){		it = prev(it);st.erase(it), nodes[i].c --, s += nodes[i].a;it = st.upper_bound(nodes[i].b);}}if(st.size()) cout << -1;else cout << s;return 0;
}

这篇关于贪心，蓝桥杯真题 [巧克力]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---