【警告】本题解是 Markdown 和 LaTeX 的结合体，请复制源码至洛谷云剪贴板/专栏/主页编辑界面查看。

这道题它求的是最值并且这玩意儿明显不用上 dp？哟呵，直接二分答案！！！

然后我就随手写了个超级炸裂的东西（$20$ pts）：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
bool f(int a[],int n,int k,int mid)
{
    int cnt=0;
    for(int i=0;i<n;i++)
    {
        cnt+=min(a[i],mid);
    }
    return cnt>=mid*k;
}
int fun(int a[],int n,int k)
{
    int L=0,R=1e9;
    int res=0;
    while(L<=R)
    {
        int mid=(L+R)>>1;
        if(f(a,n,k,mid))
        {
            res=mid;
            L=mid+1;
        }
        else
        {
            R=mid-1;
        }
    }
    return res;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,k;
        cin>>n>>k;
        int a[N];
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
        }
        int ans=fun(a,n,k);
        cout<<ans<<endl;
    }
    return 0;
}

但是这里有个很坑的地方：$n\le 2\times 10^5$，$a_i\le 10^9$，所以此处的方案数也就是 $cnt$ 可能会高达 $2\times 10^14$，所以：这玩意儿不开 long long 直接见祖宗！

但是还有个问题：如果你把右边界 $r$ 设成 $2\times 10^14$……

$k = 2\times 10^5$ 的时候直接就爆 long long 了！！！

于是我们就不得不给 $r$ 一个合理的值 $\frac{sum}{k}$ 了。

于是我们就可以把代码改成这样……

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int sum=0;
bool f(int a[],int n,int k,int mid)
{
    int cnt=0;
    for(int i=0;i<n;i++)
    {
        cnt+=min(a[i],mid);
    }
    return cnt>=mid*k;
}
int fun(int a[],int n,int k)
{
    int L=0,R=sum/k;
    int res=0;
    while(L<=R)
    {
        int mid=(L+R)>>1;
        if(f(a,n,k,mid))
        {
            res=mid;
            L=mid+1;
        }
        else
        {
            R=mid-1;
        }
    }
    return res;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,k;
        cin>>n>>k;
        int a[N];
        sum=0;
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
            sum+=a[i];
        }
        int ans=fun(a,n,k);
        cout<<ans<<endl;
    }
    return 0;
}

然后就过了。