首先我们要想:怎么才能使这些分配方式尽量平均呢? 我们来列一个表. 原来的数据 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 <bits/stdc++.h> #include<iostream> #include <algorithm> using namespace std; int a[30100]; int main(){ int n,cnt,w; cin>>w; cin>>n; int j=n; int i=1; for(int i=1;i<=n;i++){ cin>>a[i]; } sort(a+1,a+n+1); while(i<=j){ if(a[i]+a[j]<=w){ i++; j--; } else{ j--; } cnt++; } cout<<cnt; }

#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)

#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; }

要解决这个问题，我们可以使用贪心算法。首先将纪念品价格按照升序排序，然后使用双指针的方法，将价格最小的纪念品与价格最大的纪念品进行配对。如果两者价格之和小于等于给定的上限，则将它们分为一组；否则，单独将价格最大的纪念品分为一组。然后移动指针继续配对，直到指针相遇。 下面是使用 C++ 编写的示例代码：

读入之后先用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]只能单独为一组，所以贪心是 正确的。

贪心还行，不难

#include<bits/stdc++.h> using namespace std; int main(){ int w,n,g[30010]={0},cnt=0; cin>>w>>n; for(int i=0;i<n;i++){ cin>>g[i]; } sort(g,g+n); int l=0,r=n-1; while(l<=r){ if(g[l]+g[r]<=w){ l++; } r--; cnt++; } cout<<cnt; return 0; }

#include <bits/stdc++.h> using namespace std; int a[1000005]; int main(){ int w,n,sum = 0; 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[i] + a[j] <= w){ i,j--; } else{ j--; } sum++; } cout<<sum; return 0; }

有关必回关