Description
　　Windbreaker計劃送一些項鏈給他的朋友們作為新年禮物。為了表示誠意，他決定自己制作全部的項鏈。他購買了若干種珍珠，每種珍珠都有特定的顏色。他要制作的項鏈都是M-完美的，也就是每條項鏈都是恰好由M種珍珠組成的。Windbreaker想知道他最多能送出多少條項鏈。給定每種珍珠的數(shù)目，你要回答的是Windbreaker最多可以制作多少條M-完美項鏈。

Input
　　輸入包含多組測試數(shù)據。每組數(shù)據第一行是一個正整數(shù)n，代表有n種珍珠。第二行包含n個正整數(shù)，代表每種珍珠的數(shù)目。第三行包括1個正整數(shù)M，代表要制作的是M-完美項鏈。 　　輸入數(shù)據以1行n=0結束。這組數(shù)據不用處理。

Output
　　對每組測試數(shù)據，輸出一行答案，為一個整數(shù)，代表最多能制作的M-完美項鏈的數(shù)目。

Sample Input
5 3 3 3 3 3 5 6 1 2 3 4 5 6 5 0

Sample Output
3 3

Data Constraint
對20%的數(shù)據，有n<=10；

對40%的數(shù)據，有n<=100；

對100%的數(shù)據，有n<=1000,每種珍珠數(shù)目不超過2000，1<=M<=100。
.
.
.
.
.
.
分析
二分答案。
每次二分，如果最大m種珍珠數(shù)不夠當前的mid就從其他珍珠里面借。如果能湊齊m種珍珠每種數(shù)量為mid的就可以了。

.
.
.
.
.
.
程序：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;int n,a[2000],m;bool check(int x) {int tj=0;for (int i=1;i<=n-m;i++)tj+=a[i];for (int i=n-m+1;i<=n;i++)if (a[i]<x){tj-=x-a[i];if (tj<0) return false;}return true; }int ef(int l,int r) {while (l<r){int mid=(l+r+1)/2;if (check(mid)==true) l=mid; else r=mid-1;}return l; }int main() {while (scanf("%d",&n),n!=0){if (n==0) break;memset(a,0,sizeof(a));int sum=0;for (int i=1;i<=n;i++){scanf("%d",&a[i]);sum+=a[i];}scanf("%d",&m);sort(a+1,a+n+1);int ans;ans=ef(0,sum/m);printf("%d\n",ans);}return 0; }

轉載于:https://www.cnblogs.com/YYC-0304/p/11094934.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的新年礼物的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。