【HDU 6335】Problem D. Nothing is Impossible

布满荆棘的人生 2022-05-16 23:37 147阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=6335][http_acm.hdu.edu.cn_showproblem.php_pid_6335]

题意：输入n，m，a\[ i \]，b\[ i \]，n代表问题的个数，m代表学生的个数，a\[ i \]代表第i个问题的正确答案的个数，b\[ i \]代表第i个问题的错误答案的个数，问m个学生来回答这n个问题，采取最优策略，则其中的优胜者至少能得多少分，而答对一题就得一分，即就是问至少能答对多少道题。(题上说每个a\[ i \]都是1,其实是不是1都一样,不影响结果)

思路：题上说要采取最优策略，而且最终是最少能答对多少题，也就是说一定会答对的就按答对算，不确定能答对的就按错误算，最后算出来的才是最少能答对的题数。

这道题问的是优胜者最少能答对多少题，换句话说就是我们尽可能的让优胜者选正确的答案，但是由于优胜者不知道自己选的答案是否是正确答案，因此我们需要让每个人尽可能的把每个选项都选一遍，最后肯定会有一个优胜者得分最高。

比如有一道题有4个选项，其中只有1个是正确答案，另一道题有3个选项（设为A,B,C），其中只有1个是正确答案，辣么，我们来看看，如果我们想让优胜者答对2道题的话，我们需要多少个学生。

首先我们先找4个学生分别选第一道题的4个选项，然后我们再让这4个学生都选第2道题的A选项，辣么，如果A是正确答案的话，不管第1道题里面的4个选项哪个是正确答案，这4个学生中肯定会有一个学生（即优胜者）答对2题；而我们并不知道第2道题里面的3个选项中到底哪个才是正确答案，因此我们还需要再找另外4个学生，先分别选第1道题的4个选项，再都选第2道题的B选项，然后，再找其他的4个学生，先分别选第1道题的4个选项，再都选第2道题的C选项，辣么，最后在这4\*3个学生中肯定会有一个优胜者2道题全答对了。

so，要想优胜者答对2题，至少需要4\*3个学生。然后这道题是给你学生数，让你求出至少答对的题数，其实是一样的，我们让sum=1，用来记录答对i道题至少需要多少学生，然后让sum\*=（b\[ i \]+1），直到sum大于m时，此时说明给出的学生不够答对接下来的题了，此时输出i，即优胜者最少能答对的题数。

（对了，还要一点很重要，就是我们要将n道题的错误答案（即b\[ i \]）按从小到大进行排序，因为我们要采取最优策略，就尽可能的先做错误答案少的题，这样我们才能保证留下来的学生越多，这样对的题才能越多，如果你前面就把人给用完了，辣后面就没人了，这样就不是最优策略了）

My DaiMa：

#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        int t,n,a[105],b[105];
        long long int m;
        cin >> t;
        while( t-- )
        {
            scanf("%d%lld",&n,&m);
            for(int i = 0; i < n; i++)
                scanf("%d%d",&a[i],&b[i]);
            sort(b,b+n);//一定要排序，先做错误答案少的题，留更多的人去做后面的题，才能保证最优策略
            long long int sum = 1;
            int i = 0;
            for(;i < n; i++)
            {
                sum *= b[i]+1;
                if(sum > m)//直到人数超过给出的学生数时，这时候因为给出的学生都用完了，就没人了，后面的题也做不了了
                    break;
            }
            printf("%d\n",i);
        }
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_6335]: http://acm.hdu.edu.cn/showproblem.php?pid=6335