题解：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

代码

CPP

#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.

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

文章操作

大致题意

条件分析

代码

相关推荐

评论

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