关于 Bsq AK ZUCCPC的思路+代码

• OP
• 大体思路
• AC代码
• ED

题目来源：2020年浙大城市学院新生程序设计竞赛（同步赛）-H Bsq AK ZUCCPC

题目描述

新生赛开赛在即，Kwords打算预测每道题的过题人数，现在他想知道如果按照他预测的过题数据，会有多少人能够AK（全部通过）或爆零（无法通过任何一道题）呢。因为Kwords并不知道榜单实际的过题情况，所以希望你能帮助他预测AK和爆零的人数区间。

输入描述

第一行给出一个正整数T(1≤T≤10)，表示接下来会给出T组测试数据。
对于每组测试数据，第一行给出两个正整数N(1≤N≤10⁵)表示新生赛有多少个题目，M(1≤M≤10⁹ )表示参赛人数。
第二行给出N个数字，第i个数字表示第i道题通过的人数a_i (0≤a_i≤M)。

输出描述

对于每组数据，第一行给出两个数字L₁,R₁,表示AK的人数在区间[L₁,R₁]内，第二行给出两个数字L₂,R₂，表示爆零的人数在区间[L₂,R₂]内。

OP

感谢rk学长与sl学长的倾情指导。
.

大体思路

对于每道题，有a_i人A掉，有M-a_i人未A。则对于所有N道题，设A了P=a₁+a₂+…+a_n人次，未A Q=M-a₁+M-a₂+…+M-a_n人次。
对于AK左限，我们可以假设所有未A是尽可能由不同人完成的，即L₁=MAX{M-Q , 0};对于AK右限，我们可以假设A掉AC数最少题的人也A掉了其他所以题，即L₂=MIN{a_i}；对于爆零左右限同理，L₁=MIN{M-P , 0}，L₂=M-MAX{a_I} 。

两个右限可如下例直观解释，N=6，M=20：

.

AC代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main()
{
    ll t,m,n,i;
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld%lld",&n,&m);
        ll a[100005],mi=1000000000,suf=0,ma=0,sum=0;
        for(i=1; i<=n; i++)
        {
            scanf("%lld",&a[i]);
            if(a[i]<mi)mi=a[i];
            if(a[i]>ma)ma=a[i];
            sum+=a[i];
            suf+=m-a[i];
        }
        printf("%lld %lld\n%lld %lld\n",
        	((suf>m)?0:m-suf),mi,((sum>m)?0:m-sum),m-ma);
    }
    return 0;
}

ED

这套题真的太草了（双语）；
&我被吊锤；
&但我还是喜欢。