关于 Bsq AK ZUCCPC的思路+代码

关于Bsq AK ZUCCPC一题的思路+代码

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

题目描述

新生赛开赛在即，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

感谢ph姐姐与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

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

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！