首页 > 代码库 > POJ_3663_贪心
POJ_3663_贪心
题目描述：
给你一堆数和一个限定的空间大小，要求求出两个数的和小于等于空间大小的对数。
思路：
贪心，先给一堆数从大到小排序。
第一个数取数组第一个，第二个数从第二个开始依次往后取，只要某个第二个数满足，则后面的第二个数均满足。
第一个数取数组第二个，第二个数从第三个开始依次往后......
......
应该不是最高效的方法，但还是可以AC的。
#include<cstdio>#include<iostream>#include<algorithm>using namespace std;bool cmp(int a,int b){ return b<a;}int main(){ int n,s,a[20005]; cin >> n >> s; for(int i = 1;i <= n;i++) cin >> a[i]; sort(a+1,a+1+n,cmp); int num = 0; for(int i = 1;i < n;i++) { for(int j = i+1;j <= n;j++) { if(a[i]+a[j] <= s) { num += n-j+1; break; } } } cout << num << endl; return 0;}
POJ_3663_贪心
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。