Description
EYENCE有N个部门,第i个部门有Ai名员工(1≤i≤N)。没有员工属于多个部门。
该公司正在计划跨部门的项目。 每个项目将由从K个不同部门中,每个部门选出一个人,共K名员工组成。
最多可以做多少个项目? 没有哪一个员工可以参与多个项目
Format
Input
第一行给出N,K 接下来给出N个数字,代表a1....an
1≤K≤N≤2×10^5
1≤Ai≤10^12
Output
如题
Samples
输入数据 1
3 3
2 3 4
输出数据 1
2
输入数据 2
4 2
1 1 3 4
输出数据 2
4
hint 对于样例2
4 2
1 1 3 4
不妨设第1个部门的员工为a
设第1个部门的员工为b
设第2个部门的员工为c1,c2,c3
设第3个部门的员工为d1,d2,d3,d4
因为每个项目组需要2个人
于是我们可以按这个的方式进行配对(c1,d1),(c2,d2),(c3,d3),(a,b)。于是最多可以建立4个项 目组。
我以前AC的代码:
include [HTML_REMOVED]
define int long long
using namespace std;
int n,m,a[10000001],l,r,mid,ans,ss;
bool f(int x)
{
int t = 0;
for(int i = 1; i <= n; i) t += min(mid,a[i]);
return t >= mid * m;
}
signed main()
{
cin>>n>>m;
for(int i = 1; i <= n; i) scanf(“%lld”,&a[i]);
for(int i = 1; i <= n; i++) ss += a[i];
r = ss / m;
while(l <= r)
{
mid = (l + r) / 2;//mid组
if(f(mid))
{
l = mid + 1;
ans = mid;
}
else r = mid - 1;
}
cout<<ans;
return 0;
}
为啥改成y总的就错了啊(样例1没过)求大佬解释下
include [HTML_REMOVED]
define int long long
using namespace std;
int n,m,a[10000001],l,r,mid,ans,ss;
bool f(int x)
{
int t = 0;
for(int i = 1; i <= n; i) t += min(mid,a[i]);
return t >= mid * m;
}
signed main()
{
cin>>n>>m;
for(int i = 1; i <= n; i) scanf(“%lld”,&a[i]);
for(int i = 1; i <= n; i++) ss += a[i];
r = ss / m;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (f(mid)) l = mid;
else r = mid - 1;
}
cout<<l;
return 0;
}