Flowers

題目描述

Recently Jack becomes much more romantic. He would like to prepare several bunches of flowers.

Each bunch of flowers must have exactly M flowers. As Jack does not want to be boring, he hopes that flowers in the same bunch are all different species. Now there are {N}N species of flowers in the flower shop, and the number of the i-th species of flower is a_ia
i
?
. Now Jack would like to know how many bunches of flowers he can prepare at most.

\textit{(Flowers are used to propose.)}(Flowers are used to propose.)
輸入描述:
The first line contains an integer {T}T (1 \le T \le 101≤T≤10) — the number of test cases.
In the first line of each test case, there are two integers {N}N, {M}M (1 \le N, M \le 300,0001≤N,M≤300000) — the number of flowers’ species and the number of flowers in a bunch.
In the second line of each test case, there are {N}N integers — the {i}i-th integer indicates ai the number of {i}i-th species’ flowers.
輸出描述:
For each test case, output one integer in one line — the answer of the corresponding test case.
示例1
輸入
復(fù)制

1 5 3 1 1 1 2 1

輸出
復(fù)制

2

題意：

一共有n種花，每種花數(shù)量為a[i]，要用這些花來做成花束，每個花束必須正好有M多花，且都是不同品種，問最多能做成多少束花

題解：

假設(shè)能做成x束花，那么就需要花的總量為xm，一共有n種花，如果a[i]>x,也就是這種花可以用在每一束，也就是第i種花最多用x個，如果a[i]<x，那第i種花就要全部用完才可以。
我們用tot來記錄在x個花束的情況下，現(xiàn)有的能提供多少花
也就是看當(dāng)前x的情況下，每一種花所能做的貢獻(xiàn)是多少，tot為貢獻(xiàn)和
如果tot>xm，即供給大于需求，說明情況成立，最佳答案肯定大于等于x
如果tot<xm,即供給小于需求，說明情況不成立，組價答案肯等小于等于x
這樣x我們就可以用二分來確定，條件的判斷即tot與xm的關(guān)系

代碼：

#include<cstdio> #include<iostream> #include<queue> #include<set> #include<algorithm> using namespace std; const int maxn=4e5+8; typedef long long ll; ll a[maxn];int n,m; bool check(ll x)//x束花 {ll tot=0;for(int i=1;i<=n;i++)tot+=min(a[i],x);if(tot>=x*m)return 1;return 0; } int main() {ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t;cin>>t;while(t--){cin>>n>>m;ll sum=0;for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i];}ll l=0,r=sum/m,ans;while(l<=r){ll mid=(l+r)>>1;if(check(mid)){l=mid+1;ans=mid;}else r=mid-1;}cout<<ans<<endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的2020-10-03的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。