读入之后先用sort排序,然后用两个指针一起向中间走,每次选择都尽可能的让当前状态下最大的和最小的分在一组,如果不行就最大的单独分一组,这样贪心下来就是最少分的组了。证明如下:
如果最大的a[r]不与最小的a[l]分在一组,而是a[r]与a[i]在一组,a[l]与a[j]在一组,因为a[l]<=a[i]&&a[r]>=a[j],所以交换两者分组不影响后续选择,而a[r]如果不能与a[l]在一组,因为a[l]为当前最小值,所以a[r]只能单独为一组,所以贪心是 正确的。
元旦快到了,校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡,他要把购来的纪念品根据价格进行分组,但每组最多只能包括两件纪念品, 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品,乐乐希望分组的数目最少。
你的任务是写一个程序,找出所有分组方案中分组数最少的一种,输出最少的分组数目。
输入文件group.in包含n+2行:
不能用贪心算法解决,第1行包括一个整数w,为每组纪念品价格之和的上眼= 第2行为一个整数n,表示购来的纪念品的总件数G
第3-n+2行每行包含一个正整数Pi (5 <= Pi <= w3)w表示所对应纪念品的价格。
输出文件group.out仅→行,包含一个整数, ep最少的分组数目合
100 9 90 20 20 30 50 60 70 80 90
6
50%的数据满足: 1 <=n <= 15
100%的数据满足: 1 <= n <= 30000, 80 <= W <= 200
解题代码:
#include<bits/stdc++.h>
using namespace std;
int ps[30001];
int main(){int w,n,ans=0;cin>>w>>n;for(int i=0;i<n;i++)cin>>ps[i];sort(ps,ps+n);int l=0,r=n-1;while(l<=r){if(ps[l] + ps[r] <=w )l++,r--,ans++;elser--,ans++;}cout<<ans<<endl;return 0;
}
贪心算法模型?
版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间:8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态