用c++完成: # T576285 「YLLOI-R1-T1」等你下课 ## 题目背景 You can switch the language of problem description. Problem background are songs.   ## 题目描述 OI 集训了，但是同学们还想上文化课。 一共有 $k$ 节文化课，小 Y 有 $n$ 个好朋友，他的第 $i$ 个好朋友计划选择 $m_i$ 节课。由于小 Y 觉得他太强了，所以没有选择任何一节。 小 Y 好朋友们知道，当他们全都在上同一节课时，机房就只剩下小 Y 一人，此时小 Y 会感到孤独。因此好朋友们希望调整他们的选课方案，使得小 Y 的孤独时间尽可能短。请计算在最优安排下，小 Y 会感到孤独的课程数量的最小值。 ## 输入格式 第一行两个正整数 $n,k$。 第二行 $n$ 个正整数 $m_i$。 ## 输出格式 一个整数，表示在最优安排下，小 Y 会感到孤独的课程数量的最小值。 ## 输入输出样例 #1 ### 输入 #1 ``` 2 3 3 2 ``` ### 输出 #1 ``` 2 ``` ## 输入输出样例 #2 ### 输入 #2 ``` 3 4 3 3 3 ``` ### 输出 #2 ``` 1 ``` ## 输入输出样例 #3 ### 输入 #3 ``` 6 5 1 1 4 5 1 4 ``` ### 输出 #3 ``` 0 ``` ## 说明/提示 #### 【样例解释#1】 第一个好朋友选择了 $m_1=k$ 节课，因此他必须每节课都去上，没有调整选课方案的可能。 因此第二个好朋友一旦选择了一节课，这节课就会被所有好朋友选择，小 Y 也会在这节课时孤独。因此小 Y 会感到孤独的课程数量为 $m_2=2$ 节。

<think>好的，我现在得仔细看一下这个问题。题目大意是说，有n个朋友，每个朋友选了m_i节课。现在他们可以调整自己的选课，但每个朋友选的课的数量必须保持不变。也就是说，比如原来选3节课，调整后还是得选3节，但具体选哪些课可以变。我们的目标是在调整之后，所有朋友共同选的课程尽可能少。因为如果存在至少一门课是所有朋友都选的，那么小Y就会在那节课孤独。而我们要让这样的课程数量最少。 那问题转化为，如何安排每个人的选课集合，使得他们共同选课的课程数量最少。然后输出这个最小值。 首先，我得想，什么情况下他们的共同课程最少？可能的情况是尽可能分散他们的选课，使得他们的交集尽可能小。或者是否存在一种安排方式，使得他们的交集为空？比如样例3的输出是0，说明这种情况下他们可以完全不相交。 那问题的关键点在于，所有朋友的总选课数之和是否超过了k*(n-1)。或者说，是否存在一种方式，使得每个课程最多被n-1个朋友选中。如果总选课数之和不超过k*(n-1)，那么就可以这样安排，这样交集就是0。否则的话，必须有一些课程被所有n个朋友选中，这时候交集的数量就等于总选课之和 - k*(n-1)。或者这可能是一个思路？ 举个例子，假设总共有n个朋友，每个选m_i节课。总共有sum= m_1+ m_2+ ... + m_n。总共有k个课程。每个课程最多被n-1个朋友选，这样总共有k*(n-1)个位置。如果sum <= k*(n-1)，那么可以安排每个课程最多被n-1个朋友选，那么所有朋友的选课没有共同的课程。这时候答案就是0。否则的话，sum超过的部分就是必须每个课程被所有n个朋友选中的次数。比如，sum超过的部分为d，那么答案就是d。或者说，这可能吗？ 比如样例1的情况：n=2，k=3。m是3和2。总和是5。每个课程最多被1个人选的话，总共有3*1=3个位置。显然5>3，所以必须每个朋友选课的交集至少为5-3=2。所以答案是2。这与样例1的输出一致。 样例2的情况：n=3，k=4。m是3,3,3。总和是9。每个课程最多被2人选中，总共有4*2=8。总和9-8=1，所以答案是1。这与样例2的输出一致。 样例3的总和是1+1+4+5+1+4=16。n=6，每个课程最多5人选，k=5，所以总共有5*5=25。16<=25，所以可以安排，所以答案是0。 所以结论应该是，当总和sum<= k*(n-1)时，答案是0，否则是sum -k*(n-1)。 那这个问题的解法就是计算sum = sum(m_i)，然后取max(0,sum -k*(n-1))。但还需要验证每个m_i是否不超过k。比如，如果某个朋友的m_i超过了k，那是不可能的，因为每个朋友必须选恰好m_i节课，但总共有k节课。所以当存在某个m_i >k的话，这种情况无法满足。但是题目描述中输入的m_i是否是合法的？题目输入的保证应该是有解的？比如题目中的输入是否总是满足m_i<=k？例如样例1中的第一个朋友选3节课，而k=3，没问题。第二个选2，也<=3。如果存在某个m_i超过k的话，那么无法满足，但题目可能保证输入是合法的？或者题目中的每个m_i可能大于k？ 比如，假设某个朋友的m_i >k，那么他必须选k节课吗？但题目中的每个朋友选m_i节课，但总共有k节课，所以如果m_i>k的话，显然不可能，此时问题无解。但题目描述中的输入可能不会有这样的情况？ 因此，在代码中是否需要处理这种情况？ 题目中的输入描述是“第二行n个正整数m_i”，但没有说明m_i是否<=k。可能这个题目的数据是保证每个m_i <=k的。否则，问题本身无法解决，因为不可能存在这样的安排方式。 所以，在解题的时候，只需要计算sum = sum(m_i)，然后max(0,sum - k*(n-1))即可。但是如果sum超过的话，那么当sum -k*(n-1)大于0时，就是答案。否则是0。那现在代码的思路应该是： 读取n和k。 读取数组m。 计算sum = accumulate(m.begin(), m.end(), 0)然后ans = max(0, sum- k*(n-1)) 输出ans. 比如样例1中的sum=3+2=5。k*(n-1)=3*(2-1)=3.5-3=2>0，所以答案是2。 样例2：sum=9，k=4*(3-1)=8。9-8=1>0，答案是1. 样例3：sum=16，k=5*(6-1)=25。16-25是-9，取0.那这样看来，这个问题的解法非常简单，只需要计算总和减去k*(n-1)，若结果大于等于0则为结果，否则为0。 那这样是否正确？ 需要验证一下。比如假设n=1的情况下，此时k*(n-1)=0。sum是m_1。如果n=1的话，那么所有朋友必须选m_1节课，但因为每个课程必须被所有朋友选，所以小Y会在每节课孤独。所以答案是m_1。但根据公式sum-k*(n-1) =m_1 -0= m_1。这显然正确。但题目中的n是否可能等于1？题目描述中的输入条件n是正整数，可能包括1。比如测试案例：输入： 13 3输出应该是3，因为朋友必须选3节课，所以这三节课都是共同选的，小Y在这三节课孤独。 根据公式sum=3，k*(n-1)=0。3-0=3，正确。 另一个例子，假设n=3，k=5，每个m_i是5。sum=15。k*(n-1)=5*2=10。sum -10=5。所以答案是5。那总共有5门课，每个朋友选5门，这时候必须每门课都被所有三个朋友选中吗？总共有5门课，每个朋友选5门，所以必须选全部课程。所以他们的交集是5门课，答案是5，正确。 所以公式是正确的。 综上，这个题目的解法非常简单，只需要计算总和是否超过k*(n-1)。如果超过，则差值是答案，否则是0。 那现在代码就容易了。用C++的话，读取输入，求和，计算max(0,sum -k*(n-1)).那现在需要考虑的是，如何处理输入中的m_i是否超过k的问题。如果存在某个m_i>k的话，那么无法安排，因为该朋友必须选m_i门课，但总共有k门课，所以他只能选k门课。那这时候，这样的输入是否合法？题目中的输入可能是否合法？比如题目可能保证每个m_i <=k。或者题目中的描述是否允许这样的情况？ 例如题目中的输入样例中的每个m_i都是<=k的。比如样例1中的3和2都<=3，样例2中的3都<=4，样例3中的各m_i均<=5？所以可能题目中的输入数据是保证每个m_i <=k的。所以不需要处理这种情况。否则的话，题目可能无法得到正确解。 因此，在代码中不需要处理这种情况，直接按照公式计算即可。 所以，现在写代码的步骤： 读入n和k。 读入n个m_i，求和sum。 计算ans =max(0,sum - (n-1)*k). 输出ans.这个思路是正确的吗？ 是的。所以这个问题的解法非常简洁，不需要复杂的算法。 那现在编写代码即可。</think>用C++解决该问题的代码如下： ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, k; cin >> n >> k; long long sum = 0; for (int i = 0; i < n; ++i) { int m; cin >> m; sum += m; } long long ans = max(0LL, sum - (n - 1LL) * k); cout << ans << endl; return 0; } ``` **代码解释**： 1. **输入处理**：首先读取文化课数量 `k` 和朋友数量 `n`，然后读取每个朋友的选课数量 `m_i` 并累加求和。 2. **核心计算**：计算所有朋友选课总数之和 `sum`。若 `sum` 超过 `k*(n-1)`，则超出的部分即为必须被所有朋友共同选择的课程数量（即孤独时间的最小值）。否则结果为0。 3. **输出结果**：直接输出计算结果。 ---