基础贪心问题

1.部分背包问题

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
double v[N], w[N];
pair<double, int> a[N];
int n, m;int main(){cin>>n>>m;double x, y;for(int i = 0; i < n; i++){cin>>v[i]>>w[i];a[i] = {w[i] / v[i], i};}sort(a, a + n, greater<pair<double, int>>());double sum = 0, ans = 0;int i = 0;while(sum + v[a[i].second] <= m && i < n){sum += v[a[i].second];ans += w[a[i].second];i++;}if(sum < m && i < n){double x = m - sum;ans += x * a[i].first;}printf("%.2lf", ans);return 0;
}

2.排队接水

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
pair<double, int> a[N];
int n; int main(){cin>>n;double x;for(int i = 0; i < n; i++){cin>>x;a[i] = {x, i};}sort(a, a + n);double sum = 0;int m = n;for(int i = 0; i < n; i++){cout<<a[i].second + 1<<" ";m--;sum += m * a[i].first;}cout<<endl;sum /= n;printf("%.2lf", sum);return 0;
}

3.线段覆盖

按区间右端点升序排序，如果能接上就接

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e6 + 10;
pair<int, int> a[N];
int n; bool cmp(const pair<int, int>& p, const pair<int, int>& q){return p.second < q.second;
}int main(){cin>>n;int x, y;for(int i = 0; i < n; i++){cin>>x>>y;a[i] = {x, y};}sort(a, a + n, cmp);int st, ed = -1e9;int cnt = 0;for(int i = 0; i < n; i++){if(a[i].first >= ed){st = a[i].first;ed = a[i].second;cnt++;}}cout<<cnt;return 0;
}

4.合并果子

用小根堆维护最小值，每次取出两个最小值

#include<iostream>
#include<queue>
using namespace std;
priority_queue<int, vector<int>, greater<int>> q;
int n; int main(){cin>>n;int x;for(int i = 0; i < n; i++){cin>>x;q.push(x);}int sum = 0, a = 0, b = 0;while(q.size() > 1){a = q.top();q.pop();b = q.top();q.pop();sum += a + b;q.push(a + b);}cout<<sum;return 0;
}

5.小A的糖果

如果两个相邻的多了，那就先减去第二个，因为第二个还关联第三个

#include<iostream>
#include<queue>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n, m; int main(){cin>>n>>m;for(int i = 0; i < n; i++){cin>>a[i];}long long sum = 0;for(int i = 0; i < n - 1; i++){if(a[i] + a[i + 1] > m){int x = a[i] + a[i + 1] - m;if(a[i + 1] >= x) a[i + 1] -= x;else{a[i] -= x - a[i + 1];a[i + 1] = 0;}sum += x;}}cout<<sum;return 0;
}

6.删数问题

删掉下坡数

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n, m; 
string s;int main(){cin>>s;cin>>n;int len = s.size();for(int i = 0; i < len; i++){a[i] = s[i] - '0';}while(n--){for(int i = 0; i < len; i++){if(a[i] > a[i + 1]){for(int j = i; j < len; j++) a[j] = a[j + 1];len--;break;}}}int z = 0, st = 0;while(a[z] == 0 && st < len - 1){z++, st++;}for(int i = st; i < len; i++){cout<<a[i];}return 0;
}

7.陶陶摘苹果（升级版）

按花费力气升序排序，先摘花费力气小的

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
pair<int, int> q[N];
int n, m, a, b;bool cmp(const pair<int, int>& pp, const pair<int, int>& qq){if(pp.second != qq.second) return pp.second < qq.second;else return pp.first < qq.first; 
}int main(){cin>>n>>m;cin>>a>>b;int x, y;for(int i = 1; i <= n; i++){cin>>x>>y;q[i] = {x, y};}sort(q + 1, q + n + 1, cmp);int cnt = 0;for(int i = 1; i <= n; i++){if(m - q[i].second >= 0 && a + b >= q[i].first){cnt++;m -= q[i].second;}}cout<<cnt;return 0;
}

8.铺设道路

大的带着小的填，如果后面一个大于前一个高度，那就多填这个差值，最后加上第一个需要填的高度

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n;int main(){cin>>n;for(int i = 0; i < n; i++) cin>>a[i];int ans = 0; for(int i = 1; i < n; i++){if(a[i] > a[i - 1]){ans += a[i] - a[i - 1];}}ans += a[0];cout<<ans;return 0;
}

9.混合牛奶

按照价格升序排序，先买便宜的

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2e6 + 10;
pair<int, int> q[N];
int n, m;int main(){cin>>n>>m;int x, y;for(int i = 0; i < m; i++){cin>>x>>y;q[i] = {x, y};}//cout<<"-------------------"<<endl;sort(q, q + m);int ans = 0, sum = 0;for(int i = 0; i < m; i++){if(sum + q[i].second <= n){ans += q[i].first * q[i].second;sum += q[i].second;//cout<<ans<<endl;}else if(sum < n){ans += (n - sum) * q[i].first;sum = n;break;}else if(sum >= n){break;}//cout<<q[i].first<<" "<<sum<<endl;}cout<<ans;return 0;
}

10.纪念品分组

让大的和小的组合

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 3e4 + 10;
int a[N];
int n, m;int main(){cin>>m>>n;for(int i = 0; i < n; i++) cin>>a[i];sort(a, a + n, greater<int>());int cnt = 0;for(int i = 0, j = n - 1; i <= j; i++){if(a[i] + a[j] <= m){j--;}cnt++;}cout<<cnt;return 0;
}

11.跳跳！

高低高低，反复跳

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 3e4 + 10;
long long a[N];
int n, m;int main(){cin>>n;for(int i = 0; i < n; i++) cin>>a[i];sort(a, a + n, greater<int>());long long sum = 0, ed = 0;for(int i = 0, j = n - 1; i <= j; i++, j--){sum += (a[i] - ed) * (a[i] - ed);sum += (a[j] - a[i]) * (a[j] - a[i]);ed = a[j]; }cout<<sum;return 0;
}

12.分组（难）

二分查找当前满足条件的最后一个小组，如果可以进这个小组，那就进去，否则就新建一个小组

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N], q[N], siz[N];
int n, m;int main(){cin>>n;for(int i = 0; i < n; i++) cin>>a[i];sort(a, a + n);q[0] = 1e9;int cnt = 0, res = 0;for(int i = 0; i < n; i++){int l = 0, r = cnt + 1;while(l + 1 < r){int mid = (l + r) / 2;if(a[i] < q[mid]) r = mid;else l = mid;}if(a[i] == q[l]){q[l]++, siz[l]++;}else{q[++cnt] = a[i] + 1, siz[cnt] = 1;}}int ans = 1e9;for(int i = 1; i <= cnt; i++){ans = min(ans, siz[i]);}cout<<ans;return 0;
}

13.国王游戏（难）

按照左手和右手乘积升序排序，所得的奖赏之和最少

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e3 + 10;
pair<int, int> q[N];
int n, m;bool cmp(const pair<int, int>& pp, const pair<int, int>& qq){if(pp.first * pp.second != qq.first * qq.second) return pp.first * pp.second < qq.first * qq.second;else if(pp.first != qq.first) return pp.first < qq.first;else return pp.second > qq.second;
}int main(){cin>>n;int a, b;for(int i = 0; i <= n; i++){cin>>a>>b;q[i] = {a, b};}sort(q + 1, q + n + 1, cmp);long long ans = 0, sum = 0, res = 1;for(int i = 1; i <= n; i++){cout<<q[i].first<<" "<<q[i].second<<endl;res *= q[i - 1].first;sum = res / q[i].second;ans = max(ans, sum);}cout<<ans;return 0;
}