题解：P12412 「YLLOI-R1-T1」等你下课

· · 题解

原题

大致题意

在 k 门课程中选课，第 i 个学生计划选 m_i门课。当所有学生都选了同一门课时，小 Y 会感到孤独。通过调整选课方案，求最小的孤独时间段数。

条件分析

假设每个学生必须选择全部 x 门共同课程，其余课程自由选择

• 第 i 个学生自由选择课程数：m_i - x

• 所有学生自由选择总次数：\sum\limits_{i=1}^n (m_i - x)

自由选择的课程需满足：每门课最多被 n-1 个学生选择（否则会成为共同课程）。

设可供自由选择的课程数为 k - x，则有

\sum\limits_{i=1}^n (m_i - x) \leq (k - x)(n - 1)

解得

x \geq \sum\limits_{i=1}^n m_i - (n - 1)k

代码

#include<bits/stdc++.h>
using namespace std;
int n,k,a,sum;

int main(){
    cin>>n>>k;
    for (int i = 1; i<=n; i++) {
        cin>>a;
        sum+=a; // 累加所有朋友的选课总数
    }
    cout<<max(sum-(n-1)*k,0);//由于课程数量不能为负数，所以使用max函数使其至少为0
return 0;}//end.