hdu多校第七场 1006（hdu6651） Final Exam 博弈

题意：

有n道题，这n道题共m分，要求你至少做出k道才能及格，你可以自由安排复习时间，但是只有某道题复习时间严格大于题目分配的分值时这道题才能够被做出来，求最少的，能够保证及格的复习时间。复习时间和分数都是整数。

题解：

为什么给这道题一个博弈的标签呢？因为这道题其实是这样一个博弈过程：

第一回合，玩家A给自己的n个题分配复习时间

第二回合，玩家B拿到m个分数，去给题目分配分数，卡A的复习成果，只要分数和复习时间完全一样就相当于卡掉了，至少卡掉n-k+1个题B就获胜

明白了吧，学生对于题目分数分配的完全未知，其实就相当于出题老师对于学生的复习时间分配完全已知。（这有点和信息论连接起来了，以后慢慢分析）

如果你是B，怎么卡A呢？肯定是找到A复习时间最少的n-k+1个题，把m分全用在上面，都卡掉就行了。

所以，你作为A，只要保证自己复习时间最短的n-k+1道题，总和大于m就行了，这样这些题中至少有一道题B卡不掉，而B更没法舍近求远地去卡复习时间更多的题。

所以，复习时间较少的n-k+1道题，总花费时间m+1，所以复习时间第n-k+1少的题需花费$\left \lceil \frac{m+1}{n-k+1} \right \rceil$

剩下的k-1题均花费$\left \lceil \frac{m+1}{n-k+1} \right \rceil$时间来复习。

#include<bits/stdc++.h>

#define LL long long

using namespace std;

int T;

LL n,m,k;

int main()

{

    cin>>T;

    while(T--)

    {

        cin>>n>>m>>k;

        cout<<(m/(n-k+)+)*(k-)+m+<<endl;

    }

    return ;

}

巴特西

hdu多校第七场 1006（hdu6651） Final Exam 博弈

最新文章

热门文章