2 条题解
-
2
题意
有 个人,每个人的分数为 。
找到一个数 ,使每位同学的分数变为 ,我们要在新分数之和 的时候使 变得尽可能的大。
如果没有符合要求的答案输出
-1。思路
首选二分,因为有个大有个小。我们可以创建一个函数来判断当前的 ,是否能让 。但如果刚开始 ,则输出可怜的
-1。 然后二分,但 取值为多少呢?我们取个极限值 。接下来判断当前的 在函数里的布尔值是否为真,真则答案转向他,让整体值增大 ,否则整体缩小 。
温馨提示:
注意数据范围需开
long long。NODE:
#include <bits/stdc++.h> using namespace std; int n,a[1000006]; long long m; bool check(long long k){ long long s=0; for(int i=1;i<=n;i++){ if(a[i]>k)s+=a[i]-k; } return s>=m; } int main(){ cin>>n>>m; long long sum=0; for(int i=1;i<=n;i++){ cin>>a[i]; sum+=a[i]; } if(sum<m){ cout<<-1; return 0; } long long l=0,r=1000000000,ans=0; while(l<=r){ long long mid=(l+r)/2; if(check(mid)){ ans=mid; l=mid+1; } else r=mid-1; } cout<<ans; }
信息
- ID
- 4
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 显示难度普及
- 标签
- 递交数
- 5
- 已通过
- 4
- 上传者