给你n个纪念品,让你发给大家,要求每个人的纪念品数目不能超过2个,并且要使得大家获得的纪念品价值相对比较均衡,每个人的纪念品总价值不能超过m,请问最少能分出多少组。
先给纪念品的价值排个序,排序后前后同时组成纪念品组,这样能保证价值相对均衡。
AC代码如下:
#include <iostream> #include <algorithm> using namespace std; const int maxn = 3e4 + 5; int a[maxn], n, w, ans; int main(){ cin >> w >> n; for(int i = 0;i < n;i++) cin >> a[i]; sort(a, a + n); int i = 0,j = n - 1; while(i <= j){ if(a[j] + a[i] <= w){ i++, j--; ans++; }else j--, ans++; } cout << ans; return 0; }
每位奶农每天只能提供一定量的牛奶,并且他们的单价不同,现在给你一个需求,问你最少花费的多少钱能买到你需要的牛奶量。
他给你的是单价,你就按照单价排序,然后从最便宜开始,依次购买。一旦发现买多了,就退还到上一步操作,对目前可以购买的最小单价去买你还需要的那部分即可。
思考:如果是给你总价呢?你就计算性价比,按照性价比排序即可。
思考:如果对购买的公司家数有限制呢?那这就是一种动态规划的问题了。后面再去补充。
AC代码如下:
#include <iostream> #include <algorithm> using namespace std; const int maxn = 2e6 + 5; struct Node{ int p, b; }a[maxn]; int n, m, ans, cnt; bool cmp(Node n1, Node n2){ return n1.p < n2.p; } int main(){ cin >> m >> n; for(int i = 0;i < n;i++) cin >> a[i].p >> a[i].b; sort(a, a + n, cmp); for(int i = 0;i < n;i++){ cnt += a[i].b; if(cnt >= m){ cnt -= a[i].b; ans += (m - cnt)*a[i].p; break; }else ans += a[i].b*a[i].p; } cout << ans; return 0; }
给你一个时间表,上面有n个日程计划,每个日程计划对应着它的起止时间。你没有分身术,不能同时去参加两个活动,问你最多能参加多少个活动?
这题显然是一种贪心,但是如何去确定你的贪心策略呢?一个日程,我们可以得到三个关于它的属性:开始时间、结束时间、经历时长。
策略一:如果按照开始时间去排序,也许一个活动,它开始的时间很早,但是它结束的时间很晚,那肯定也不能选取,第一种方案pass!
策略二:
如果按照经历的时长去排序,时间短的活动也许覆盖住了很多时间长的活动,这也是不合理的。
于是我们确定了最终的贪心方案,按照结束时间去排序。
排序完成之后呢?我们可以确定的是,最早结束的活动我们一定是要参加的,因为参加它之后我们再去参加其他活动不会影响最优解。那么如何去确定下一个活动我们是否能够参加呢?只需要比较上一个活动结束的时间和下一个活动开始的时间,如果开始的时间在结束的时间的后面,那么这个活动就可以去参加。然后下一个活动就变成了当前活动,一次类推即可!
AC代码如下:
#include <iostream> #include <algorithm> using namespace std; const int maxn = 1e6 + 5; struct Time{ int a, b; }t[maxn]; int n, ans, pos; bool cmp(Time n1, Time n2){ return n1.b <= n2.b; } int main(){ cin >> n; for(int i = 0;i < n;i++) cin >> t[i].a >> t[i].b; sort(t, t + n, cmp); ans = 1, pos = t[0].b; for(int i = 1;i < n;i++){ if(t[i].a >= pos){ pos = t[i].b; ans++; } } cout << ans; return 0; }
这个题的做法和上面那个例题完全一样,我就不写思路了,AC代码附上:
#include <iostream> #include <algorithm> using namespace std; const int maxn = 105; int n, pos, ans; struct Node{ int beg, en; }a[maxn]; bool cmp(Node n1, Node n2){ return n1.en <= n2.en; } int main(){ while(cin >> n && n){ ans = 1; for(int i = 0;i < n;i++) cin >> a[i].beg >> a[i].en; sort(a, a + n, cmp); pos = a[0].en; for(int i = 1;i < n;i++){ if(a[i].beg >= pos){ ans++; pos = a[i].en; } } cout << ans << endl; } return 0; }
他有n个作业要写,每个作业具有一下属性:截止时间、扣的分数
最理想的情况就是所有作业都能做完,这样扣的分数最少。但是现实情况可能难以如此理想,所以我们要制定一个优先顺序,哪样的作业要先去做。因为每个作业都有截止日期,所以最着急的肯定就是马上就要去交的作业,所以截止时间最优先;那如果截止时间相同呢?那必然就去做扣分最严重的那一门科目。这个道理是显然的,我们就按此顺序去排序。
排好序之后,我们指定一个时间以天数为单位:k = 1,意思就是从第一天开始去安排做作业的顺序(因为每个作业都要做一天!)
如果到了某一天,有作业交不上了,我们就怀疑是不是之前安排的不妥当,所以去检查前面的安排,查到一个扣分最少的作业,去取代不能完成扣分又较多的那个作业,即可!
AC代码如下:
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int maxn = 1005; int t, n; struct Class{ int day, score; int book;//完成状态 }c[maxn]; bool cmp(Class n1, Class n2){ if(n1.day != n2.day) return n1.day < n2.day; return n1.score > n2.score; } int main(){ cin >> t; while(t--){ cin >> n; for(int i = 1;i <= n;i++) cin >> c[i].day; for(int i = 1;i <= n;i++){ cin >> c[i].score; c[i].book = 1;// 先假设都可以完成 } sort(c + 1, c + n + 1, cmp); int ans = 0, k = 1; for(int i = 1;i <= n;i++){ if(c[i].day >= k){ k++;//该作业可以当天完成,安排下一个的作业 continue; } int pre = c[i].score, pos = i;// 第i个作业无法当天完成 for(int j = 1;j <= i;j++){ if(pre > c[j].score && c[j].book){ pre = c[j].score; pos = j; } } ans += pre; c[pos].book = 0; } cout << ans << endl; memset(c,0,sizeof(c)); } return 0; }
一个桌子从一个房间移动到另一个房间可以在十分钟内完成,从房间 I 移动到房间 J 的时候,除了[I,J]的部分,其他部分桌子的移动是可以同时进行的。这个题其实很简单啊,就是尽可能地让更多的桌子在相应的移动区间同时移动。然后计算最少用时,所谓最少用时,其实就是最少移动次数乘以10即可。那究竟如何才能知道最少移动次数呢?这里有个坑,大家先看看这幅图:
请仔细观察房间分布
如果我有两个桌子,分别从:1 -> 3,4 -> 5看似这两个移动是不重叠的,实际上重叠了,因为3和4号房间是相对的,他们共用了这段走廊。
而且,移动的方向也不一定是从小房间到大房间,也可能是从大房间到小房间.所以我先需要两步处理:第一、让上下房间位置相对的房间号一致;第二、因为无论是大号房间到小号房间或者是反过来,走过的走廊都是一样的,所以如果是逆序则交换。
存储好了之后,重点来了:我们首先按照路径的起点排序,然后和之前的区间调度方法一样,只是说需要反复使用区间调度,每次都尽可能多的去解决问题,直到所有需要搬桌子的房间都完成了,那么也就完成这次的反复区间调度。
AC代码如下:
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int maxn = 205; int n, t, x, y; struct Node{ int beg, en; int book; }a[maxn]; bool cmp(Node n1, Node n2){ return n1.beg < n2.beg;//一定要按照起点排序 } int main(){ cin >> t; while(t--){ cin >> n; for(int i = 0;i < n;i++){ cin >> x >> y; if(x % 2) x++; if(y % 2) y++;// 使得上下房间号位置参考一致 a[i].beg = min(x, y); a[i].en = max(x, y); } sort(a, a + n, cmp); int flag = 1, cnt = 0, next; while(flag){ next = -1; flag = 0; for(int i = 0;i < n;i++){ if(a[i].beg > next && !a[i].book){ next = a[i].en; a[i].book = 1; flag = 1; } } cnt++; } --cnt; cout << cnt*10 << endl; memset(a,0,sizeof(a)); } return 0; }
给定了一个长度为n的区间,再给出m条线段的左端点和右端点,问最少使用多少条线段可以将整个区间覆盖?贪心的思路就是尽量找出更长的线段。一般是这样的解题步骤:
一、把每个线段按照左端点升序排序
二、假设已经覆盖的区间是[left,right],在剩下的线段种找出所有左端点小于等于right且右端点最大的线段,把这个线段加入到已经覆盖了的区间上,更新完成覆盖的区间。然后不断重复这个操作。