Algorithm6 贪心问题
[TOC]
贪心问题
装袋问题：
结构体排序问题 // 排序贪心：
装袋问题-每个袋子限制个数为两个
https://www.luogu.com.cn/problem/P1094
题目大意：给出若干个不同容量的东西，给出限定的最大容量的袋子，然后最少用多少个袋子装完这些不同容量东西
思路1【错误】：维护一个优先队列，每次取顶上两个，然后放一块。不行的原因，一些特殊情况，例如袋子100，物品分别为20、20、30、50、60，如果顺次加起来的话，=>30、40、50、60=>50、60、70，最后三个袋子，最少装袋是两个，20+20+60和30+50。
priority_queue<int, vector<int>, greater<int>> pq;
int main() {
scanf("%d%d", &k, &n);
for (int i = 0; i < n; ++i) {
scanf("%d", &tem);
pq.push(tem);
}
while (true){
int tmp1 = pq.top();pq.pop();
int tmp2 = pq.top();pq.pop();
cout<<tmp1<<" "<<tmp2<<endl;
if (tmp1 + tmp2 > k) {pq.push(tmp1);pq.push(tmp2);break;}
else pq.push(tmp1+tmp2);
}
printf("%d\n", pq.size());
return 0;
}
思路2【正确】：由于题目还有一个附加条件=>每个袋子最多两个（=>也在一定程度上约束了两个）用双指针，首尾各一个，分别用来指代放在袋子的两个：够了就放一个袋子里，指针都往中间移动；不够就只把大的往中间移。前提是排好序
#include <iostream>
using namespace std;
#define maxn 30010
int k, n, tem, a[maxn], ans = 0;
#include <algorithm>
int main() {
scanf("%d%d", &k, &n);
for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
sort(a, a+n);
int fidx = 0, eidx = n-1;
while (fidx <= eidx)
if (a[fidx] + a[eidx] <= k) fidx++, eidx--, ans++;
else eidx--, ans++;
printf("%d\n", ans);
return 0;
}
装袋问题-无限制个数的装袋
排序贪心
https://www.luogu.com.cn/problem/P2240
1、结构体排序，重载运算符；
2、注意点：在重载运算符的时候，存在单位**的，意思就是需要作比的，注意精度问题=>尽量把除法转换成乘法
按照单位质量排序
struct node {
int cost, val;
// bool operator < (const node n) const{return val/cost < n.val/n.cost;} // 除法的话要注意精度问题
bool operator < (const node n) const{return val*n.cost < n.val*cost;} // 转换为乘法即可AC
};
AC代码：
#include <iostream>
using namespace std;
int n, m, ta, tb, sum;
double ans;
struct node {
int cost, val;
bool operator < (const node n) const{return val*n.cost < n.val*cost;}
};
#include <queue>
priority_queue<node> pq;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d%d", &ta, &tb);
pq.push((node) {ta, tb});
}
while (!pq.empty() && sum < m) {
node nw = pq.top();pq.pop();
ans += (m-sum>=nw.cost?nw.val:(m-sum)*nw.val*1.0/nw.cost);
sum += (m-sum>=nw.cost?nw.cost:m-sum);
}
printf("%.2lf\n", ans);
return 0;
}
https://www.luogu.com.cn/problem/P1230
题目大意：给定若干个任务，给出每个任务完成的最后期限+价值，然后每个时间点只能完成一个任务。那么这些任务列表怎么排序去完成才能让价值最大化
按照价值排序，由高到低
每次遍历到之后，维护一个vis数组，来选择他的位置，贪心的选取当前位置或者往前面的最靠近当前位置的
#include <iostream>
using namespace std;
const int maxn = 5e2+9;
int n, m, vis[maxn];
struct node {
int t, v;
bool operator < (const node n) const {return v > n.v;}
}a[maxn];
#include <algorithm>
int main() {
scanf("%d%d", &m, &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i].t);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i].v);
sort(a+1, a+1+n);
for (int i = 0; i <= n; ++i) {
int idx = a[i].t;
while (vis[idx] && idx) idx--;
if (idx) vis[idx] = 1;
else m-=a[i].v;
}
printf("%d\n", m);
return 0;
}