贪心问题汇总(适配于省赛)
1、区间选点
2、最大不相交区间数量
3、区间分组
4、区间覆盖
5、区间合并
6、合并果子
【扩展题】：整数删除
// /*
// * @Author: YMYS
// * @Date: 2025-03-29 21:08:29
// * @LastEditTime: 2025-04-09 20:22:23
// * @FilePath: \VScode-C&C++-Coding\Acwing\算法基础课\第六章\简单贪心问题汇总.cpp
// * @URL:
// * @Description: 贪心问题汇总
// */
一、区间问题
1.1、区间选点
// //一、区间问题
// //1-区间选点
// //https://www.acwing.com/problem/content/907/
// #include<bits/stdc++.h>
// #define int long long
// #define err cout << "error" << endl
// using namespace std;
// const int N = 1e5 +10;
// // int T;
// // void solve(){
// // }
// struct node{
// int l;
// int r;
// bool operator< (const node &a){
// return a.r>r;
// };
// };
// int n;
// vector<node> nd;
// signed main()
// {
// #ifdef ABC
// freopen("D:/daily_Coding/VScode-C&C++-Coding/in.in", "r", stdin);
// freopen("D:/daily_Coding/VScode-C&C++-Coding/out.out", "w", stdout);
// #endif
// std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
// // cin>>T;
// // while(T--){
// // solve();
// // }
// cin>>n;
// for(int i=0;i<n;i++){
// int l,r;
// cin >> l >> r;
// nd.push_back({l,r});
// }
// sort(nd.begin(), nd.end());
// int r = -2e9;
// int res = 0;
// for(auto t : nd){
// if(t.l>r){
// r = t.r;
// res++;
// }
// }
// cout<<res<<endl;
// return 0;
// }
1.2、最大不相交区间数量
// //2-最大不相交区间数量
// https://www.acwing.com/problem/content/910/
// #include<bits/stdc++.h>
// #define int long long
// #define err cout << "error" << endl
// using namespace std;
// const int N = 1e5 +10;
// // int T;
// // void solve(){
// // }
// struct node{
// int l,r;
// bool operator< (const node & a){
// return a.l > l;
// }
// }nd[N];
// int n;
// signed main()
// {
// #ifdef ABC
// freopen("D:/daily_Coding/VScode-C&C++-Coding/in.in", "r", stdin);
// freopen("D:/daily_Coding/VScode-C&C++-Coding/out.out", "w", stdout);
// #endif
// std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
// // cin>>T;
// // while(T--){
// // solve();
// // }
// cin>>n;
// for(int i=0;i<n;i++){
// cin >> nd[i].l >> nd[i].r;
// }
// sort(nd, nd+n);
// // for(int i=0;i<n;i++){
// // cout<<nd[i].l<<endl;
// // }
// // cout<<endl<<endl;
// int r = -2e9;
// int ans = 0;
// for(int i=0;i<n;i++){
// if(nd[i].l > r){
// r = nd[i].r;
// ans++;
// }else{
// r = min(r, nd[i].r);//因为没加新区间,就得保证选的点是满足两个区间的
// }
// }
// cout<<ans<<endl;
// return 0;
// }
1.3、区间分组
// //3-区间分组
// https://www.acwing.com/problem/content/908/
// #include<bits/stdc++.h>
// #define int long long
// #define err cout << "error" << endl
// using namespace std;
// const int N = 1e5 +10;
// // int T;
// // void solve(){
// // }
// struct node{
// int l,r;
// bool operator< (const node & a){
// return a.l > l;
// }
// }nd[N];
// int n;
// priority_queue<int, vector<int>, greater<int>> p;//建立小根堆,放r
// signed main()
// {
// #ifdef ABC
// freopen("D:/daily_Coding/VScode-C&C++-Coding/in.in", "r", stdin);
// freopen("D:/daily_Coding/VScode-C&C++-Coding/out.out", "w", stdout);
// #endif
// std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
// // cin>>T;
// // while(T--){
// // solve();
// // }
// cin>>n;
// for(int i=0;i<n;i++){
// cin >> nd[i].l >> nd[i].r;
// }
// sort(nd, nd+n);
// p.push(-2e9);
// // int ans = 0;//此题不需要该变量
// for(int i=0;i<n;i++){
// if(nd[i].l > p.top()){
// p.pop();
// p.push(nd[i].r);
// // ans++;
// }else{
// p.push(nd[i].r);
// }
// }
// cout<<p.size()<<endl;
// return 0;
// }
1.4、区间覆盖
// //4-区间覆盖
// //https://www.acwing.com/problem/content/909/
// #include<bits/stdc++.h>
// #define int long long
// #define err cout << "error" << endl
// using namespace std;
// const int N = 1e5 +10;
// // int T;
// // void solve(){
// // }
// int s,t,n;
// //int a[N], b[N];
// struct node{
// int l,r;
// bool operator< (const node &a){
// return l<a.l;
// }
// }nd[N];
// signed main()
// {
// #ifdef ABC
// freopen("D:/daily_Coding/VScode-C&C++-Coding/in.in", "r", stdin);
// freopen("D:/daily_Coding/VScode-C&C++-Coding/out.out", "w", stdout);
// #endif
// std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
// // cin>>T;
// // while(T--){
// // solve();
// // }
// cin>>s>>t>>n;
// for(int i=0;i<n;i++){
// cin >> nd[i].l >> nd[i].r;
// }
// sort(nd, nd+n);
// int res = 0;
// // bool sucess = false;
// for(int i=0;i<n;i++){
// int j = i, r = -2e9;
// while(j<n && nd[j].l<=s){
// r = max(r, nd[j].r);
// j++;
// }
// if(r < s){
// cout<<-1<<endl;
// return 0;
// }
// res++;
// if(r >= t){
// s = r;
// break;
// }
// s = r;
// i = j-1;
// }
// if(s>=t) cout << res << endl;
// else cout<<-1<<endl;
// return 0;
// }
1.5、区间合并
// //5-区间合并
// //https://www.acwing.com/problem/content/805/
// #include<bits/stdc++.h>
// #define int long long
// #define err cout << "error" << endl
// using namespace std;
// const int N = 1e5 +10;
// // int T;
// // void solve(){
// // }
// int n;
// vector<pair<int, int>> vc;
// vector<pair<int, int>> xx;
// signed main()
// {
// #ifdef ABC
// freopen("D:/daily_Coding/VScode-C&C++-Coding/in.in", "r", stdin);
// freopen("D:/daily_Coding/VScode-C&C++-Coding/out.out", "w", stdout);
// #endif
// std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
// // cin>>T;
// // while(T--){
// // solve();
// // }
// cin>>n;
// for(int i=0;i<n;i++){
// int l,r;
// cin>>l>>r;
// vc.push_back({l,r});
// }
// sort(vc.begin(), vc.end());
// int l = -2e9, r = -2e9;
// for(auto it : vc){
// int t = it.first;
// if(t>r){
// if(l != -2e9) xx.push_back({l,r});//放入上一条线段
// l = it.first;
// r = it.second;
// }else{
// r = max(r, it.second);
// }
// }
// if(l!=-2e9) xx.push_back({l,r});
// cout<<xx.size()<<endl;
// return 0;
// }
二、Huffman树
2.1、合并果子
// //二、Huffman树
// //2.1、合并果子
// //https://www.acwing.com/problem/content/150/
// /*
// * @Author: YMYS
// * @Date: 2025-04-09 16:40:34
// * @LastEditTime: 2025-04-09 17:41:29
// * @FilePath: \VScode-C&C++-Coding\Acwing\算法基础课\第六章\Huffman树\1.合并果子.cpp
// * @URL:https://www.acwing.com/problem/content/150/
// * @Description: 148. 合并果子
// *
// *
// * 这道题和【整数删除】很像，链接如下
// * //https://www.acwing.com/file_system/file/content/whole/index/content/10768190/
// * //https://www.lanqiao.cn/problems/3515/learning/
// *
// *
// */
// //小根堆做法【O(nlogn)】
// #include<bits/stdc++.h>
// #define int long long
// #define err cout << "error" << endl
// using namespace std;
// typedef pair<int,int> PII;
// const int N = 1e4 + 10;
// // int T;
// // void solve(){
// // }
// int n;
// int a[N];
// priority_queue<int , vector<int>, greater<int>> p;//小根堆
// signed main()
// {
// #ifdef ABC
// freopen("D:/daily_Coding/VScode-C&C++-Coding/in.in", "r", stdin);
// freopen("D:/daily_Coding/VScode-C&C++-Coding/out.out", "w", stdout);
// #endif
// std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
// // cin>>T;
// // while(T--){
// // solve();
// // }
// cin>>n;
// for(int i=1;i<=n;i++){
// cin>>a[i];
// p.push(a[i]);
// }
// int sum = 0;
// while (p.size()>1)
// {
// int xx = p.top();
// p.pop();
// int yy = p.top();
// p.pop();
// sum += xx+yy;
// p.push(xx+yy);
// }
// cout<<sum<<endl;
// return 0;
// }
三、排序不等式
3.1、排队打水
// //三、排序不等式
// //3.1、排队打水
// //https://www.acwing.com/problem/content/description/915/
// /*
// * @Author: YMYS
// * @Date: 2025-04-09 17:42:11
// * @LastEditTime: 2025-04-09 17:48:22
// * @FilePath: \VScode-C&C++-Coding\Acwing\算法基础课\第六章\3.排序不等式\1.排队打水.cpp
// * @URL:https://www.acwing.com/problem/content/description/915/
// * @Description: 913. 排队打水
// *
// * 贪心 + 模拟 + 排序
// *
// */
// #include<bits/stdc++.h>
// #define int long long
// #define err cout << "error" << endl
// using namespace std;
// const int N = 1e5 +10;
// // int T;
// // void solve(){
// // }
// int n;
// vector<int> vc;
// signed main()
// {
// #ifdef ABC
// freopen("D:/daily_Coding/VScode-C&C++-Coding/in.in", "r", stdin);
// freopen("D:/daily_Coding/VScode-C&C++-Coding/out.out", "w", stdout);
// #endif
// std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
// // cin>>T;
// // while(T--){
// // solve();
// // }
// cin>>n;
// for(int i=1;i<=n;i++){
// int x;
// cin>>x;
// vc.push_back(x);
// }
// sort(vc.begin(), vc.end());
// int sum = 0, res = 0;
// for(int i=0;i<vc.size();i++){
// // res+=vc[i];
// sum+=vc[i]*(n-i-1);
// }
// cout<<sum<<endl;
// return 0;
// }
四、绝对值不等式
4.1、货仓选址
// //四、绝对值不等式
// //4.1、货仓选址
// //https://www.acwing.com/problem/content/106/
// /*
// * @Author: YMYS
// * @Date: 2025-04-09 17:55:33
// * @LastEditTime: 2025-04-09 18:39:49
// * @FilePath: \VScode-C&C++-Coding\Acwing\算法基础课\第六章\4.绝对值不等式\1.货仓选址.cpp
// * @URL:https://www.acwing.com/problem/content/106/
// * @Description: 104. 货仓选址
// *
// *
// *
// */
// #include<bits/stdc++.h>
// #define int long long
// #define err cout << "error" << endl
// using namespace std;
// const int N = 1e5 +10;
// // int T;
// // void solve(){
// // }
// int n;
// vector<int> a;
// signed main()
// {
// #ifdef ABC
// freopen("D:/daily_Coding/VScode-C&C++-Coding/in.in", "r", stdin);
// freopen("D:/daily_Coding/VScode-C&C++-Coding/out.out", "w", stdout);
// #endif
// std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
// // cin>>T;
// // while(T--){
// // solve();
// // }
// cin>>n;
// for(int i=0;i<n;i++){
// int x;
// cin>>x;
// a.push_back(x);
// }
// sort(a.begin(), a.end());
// int sum = 0;
// int x = a[a.size()/2];
// for(int i=0;i<n;i++){
// sum += abs(a[i] - x);
// }
// cout << sum <<endl;
// return 0;
// }
五、推公式
5.1、耍杂技的牛
// //五、推公式
// //5.1、耍杂技的牛
// //https://www.acwing.com/problem/content/127/
// /*
// * @Author: YMYS
// * @Date: 2025-04-09 17:55:43
// * @LastEditTime: 2025-04-09 19:51:29
// * @FilePath: \VScode-C&C++-Coding\Acwing\算法基础课\第六章\5.推公式\1.耍杂技的牛.cpp
// * @URL:https://www.acwing.com/problem/content/127/
// * @Description: 125. 耍杂技的牛
// *
// * 推荐看题解证明
// *
// * 感悟：要多多的看数据分析，去猜贪心怎么做。然后自己建几组数据去测试一下
// *
// */
// #include<bits/stdc++.h>
// #define int long long
// #define err cout << "error" << endl
// using namespace std;
// typedef pair<int,int> PII;
// const int N = 5e4 +10;
// // int T;
// // void solve(){
// // }
// int n;
// PII a[N];
// signed main()
// {
// #ifdef ABC
// freopen("D:/daily_Coding/VScode-C&C++-Coding/in.in", "r", stdin);
// freopen("D:/daily_Coding/VScode-C&C++-Coding/out.out", "w", stdout);
// #endif
// std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
// // cin>>T;
// // while(T--){
// // solve();
// // }
// cin>>n;
// for(int i=1;i<=n;i++){
// int w,s;
// cin>>w>>s;
// a[i] = {w+s, s};
// }
// sort(a+1, a+n+1);
// int sum = -1e9;
// int res = 0;
// for(int i=1;i<=n;i++){
// int x = a[i].first, s = a[i].second, w = x-s;
// res += w;
// sum = max(sum, res-w-s);
// // cout << "w:" <<w<<" s:"<<s<<endl;
// }
// cout<<sum<<endl;
// return 0;
// }
