HDU 6335.Problem D. Nothing is Impossible-思维题 (2018 Multi-University Training Contest 4 1004)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

6335.Problem D. Nothing is Impossible

题意:给你n道题目，m个人，每题有x个正确选项，y个错误选项，问你做对题数量最多的人做对了多少道题目。

如果一道题有y个错误选项，那么我需要至少y+1个人才能保证一定有一个人做对了这道题目，所以题面上给的正确选项的数量x并没有什么实质性的作用。。。

假设第一题错误选项有y1个，第二题错误选项有y2个，那么怎么才能保证至少有一个人两道题目都做对了呢？

首先我需要至少y1+1个人才能保证一定有一个人做对了第一题，那么，我在做第二题的时候，我先让y1+1个人选了第一题，然后让他们都去选第二题的第一个错误选项，那么有一个人一定做对了一道题(第一题)，然后我再让y1+1个人选了第一题之后都去选第二题的第二个错误选项，那么这y1+1个人里面也是一定有一个人做对了一道题，直到我把第二题的所有错误选项都让人选完之后，再来y1+1个人，我才能保证一定会有一个人两道题目都做对了，OK不？所以要保证一定有一个人两道题目都做对了，我需要(y1+1)*(y2+1)个人，才能保证一定有一个人两道题目都做对了。所以按照这个思路，一直到做第i个题目的时候，一定有一个人这I道题目都做对了，因为我需要最优情况，所以错误选项数量少的才能保证我做对的题目数量会多一些，所以直接对错误选项的数量进行排序，从小到大，就可以得到最多的做对题的数量。

语文不好，不知道解释的清不清楚。

官方题解:

直接代码吧:

 //1004-6335-思维题

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #include<cassert>

 using namespace std;

 typedef long long ll;

 const int maxn=+;

 int a[maxn];

 int main()

 {

     int t;

     scanf("%d",&t);

     while(t--){

         int n,m;

         scanf("%d%d",&n,&m);

         memset(a,,sizeof(a));

         for(int i=;i<=n;i++){

             int x,y;

             scanf("%d%d",&x,&y);

             a[i]=y+;

         }

         sort(a+,a++n);

         ll sum=;int ans=;

         for(int i=;i<=n;i++){

             sum*=a[i];

             if(sum<m) ans++;

             else break;

         }

         printf("%d\n",ans);

     }

 }