竞赛
考级
首先我们要想:怎么才能使这些分配方式尽量平均呢? 我们来列一个表. 原来的数据 1 3 2 4 5 6 进行排序后的数据 1 2 3 4 5 6 然后我们把1和6,2和5,3和4配对起来,此时他们的和都是相同的,并且做到了最少的分组! 但是事实是如此吗? 如果排序后的最大价值是 10,而数据是1,4,7,10,此时1+10就过大了! 怎么办? 很简单!只要把10单独放一组,1和下一个符合要求的数字一组就行了! 上代码
树上结了西瓜
#include<bits/stdc++.h> using namespace std; int main(){ long long w,n,a[30000],sum=0; cin>>w>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } sort(a+1,a+n+1); long long i=1,j=n; while(i<j){ if(a[i]+a[j]<=w){ i++; } j--; sum++; }
法兰西玫瑰
#include<ostream> #include<algorithm> int w,n,a[30001],s,i=1; int main(){ scanf("%d%d",&w,&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]),++s; std::sort(a+1,a+n+1); for(int j=n;j>i;--j) if(a[i]+a[j]<=w) --s,++i; printf("%d",s); }
史莱克七怪
林子慷
这道题有一个条件,就是每组最多有两件纪念品,那么我们可以这样想,最大的加上最小的,如果超过上限,则最大的单独一组,再把第二大的加上最小的,如果没有超过上限,则两者为一组,再向内推进。 可设 i = 1, j = n; 假如 i<=j 按上述条件推进 欢迎加入团队
唱跳坤
先排个序,用双指针 如果i+j大于限定价格,就只拿j 时间复杂度:O(nlog2n)O(nlog_2n)O(nlog2 n)
超级大帅童……瑞*
要解决这个问题,我们可以使用贪心算法。首先将纪念品价格按照升序排序,然后使用双指针的方法,将价格最小的纪念品与价格最大的纪念品进行配对。如果两者价格之和小于等于给定的上限,则将它们分为一组;否则,单独将价格最大的纪念品分为一组。然后移动指针继续配对,直到指针相遇。 下面是使用 C++ 编写的示例代码:
鸭鸭
#include <iostream> #include <algorithm> using namespace std; int main() { int a[30009], m, n, c = 0, i, l = 1, r; cin >> m; cin >> n; r = n; for(i = 1; i <= n; i++) { cin >> a[i]; } sort(a + 1, a + n + 1); while(l <= r) { if(a[l] + a[r] <= m) { l++; r--; c++; } else { r--; c++; } } cout << c; return 0; }
Wz🕊
贪心还行,不难
阿周的小腿肉;̨̡͇̲͙̞̺̪̯
嫌疑を避ける ~~
嘎了
读入之后先用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]只能单独为一组,所以贪心是 正确的。
AC君
远在天边的浪子
有关必回关
海上生明月