Description n个节目，每个节目得分是max(a[i]-(k-1)b[i],1)，问演m个节目能够得到的最多分数是多少 Input 第一行两个整数n和m分别表示节目数和要表演的节目数，之后n个整数a[i]和n个整数b[i] (1<=n<=1e5,0<=m<=1e9,1<=a[i],b[i]<=1e9) Output 输出最大得分 Sample Input 3 6 9 7 17 1 2 3 Sample Output 67 Solution 二分找到最大的ans，使得当所有节目的分数都小于ans时至少需要表演m场，那么若使得所有节目的分数都小于ans+1时需要表演小于m场，而这些场的得分可以通过等差数列求和得到，之后可能会有一些场接着表演，这些场的分数必然是max(ans,1)，所以加上这些分数即可 Code
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<queue> #include<map> #include<set> #include<ctime> using namespace std; typedef long long ll; #define INF 0x3f3f3f3f #define maxn 111111 int n; ll m,a[maxn],b[maxn]; bool check(ll x) { ll t=0; for(int i=1;i<=n;i++) if(a[i]>=x)t+=(a[i]-x)/b[i]+1; if(t>=m)return 1; return 0; } int main() { while(~scanf("%d%I64d",&n,&m)) { for(int i=1;i<=n;i++)scanf("%I64d",&a[i]); for(int i=1;i<=n;i++)scanf("%I64d",&b[i]); if(m==0) { printf("0\n"); continue; } ll l=0,r=1e9,mid,ans=0; while(l<=r) { mid=(l+r)/2; if(check(mid))ans=mid,l=mid+1; else r=mid-1; } ll res=0,num=0; for(int i=1;i<=n;i++) if(a[i]>=ans+1) { ll k=(a[i]-ans-1)/b[i]+1; num+=k; res+=k*a[i]-k*(k-1)/2*b[i]; } res+=1ll*(m-num)*max(1ll,ans); printf("%I64d\n",res); } return 0; }