PTA:L1-088 静静的推荐

客官°小女子只卖身不卖艺 2024-03-16 22:10 74阅读 0赞

### 题目： ###

[https://pintia.cn/problem-sets/994805046380707840/exam/problems/1518582000729911296![icon-default.png_t_N5K3][]https://pintia.cn/problem-sets/994805046380707840/exam/problems/1518582000729911296][https_pintia.cn_problem-sets_994805046380707840_exam_problems_1518582000729911296_icon-default.png_t_N5K3_https_pintia.cn_problem-sets_994805046380707840_exam_problems_1518582000729911296]

天梯赛结束后，某企业的人力资源部希望组委会能推荐一批优秀的学生，这个整理推荐名单的任务就由静静姐负责。企业接受推荐的流程是这样的：

*  只考虑得分不低于 175 分的学生；
 *  一共接受 K 批次的推荐名单；
 *  同一批推荐名单上的学生的成绩原则上应严格递增；
 *  如果有的学生天梯赛成绩虽然与前一个人相同，但其参加过 PAT 考试，且成绩达到了该企业的面试分数线，则也可以接受。

给定全体参赛学生的成绩和他们的 PAT 考试成绩，请你帮静静姐算一算，她最多能向企业推荐多少学生？

#### 输入格式： ####

输入第一行给出 3 个正整数：N（≤105）为参赛学生人数，K（≤5×103）为企业接受的推荐批次，S（≤100）为该企业的 PAT 面试分数线。

随后 N 行，每行给出两个分数，依次为一位学生的天梯赛分数（最高分 290）和 PAT 分数（最高分 100）。

#### 输出格式： ####

在一行中输出静静姐最多能向企业推荐的学生人数。

#### 输入样例： ####

10 2 90
    203 0
    169 91
    175 88
    175 0
    175 90
    189 0
    189 0
    189 95
    189 89
    256 100

#### 输出样例： ####

#### 样例解释： ####

第一批可以选择 175、189、203、256 这四个分数的学生各一名，此外 175 分 PAT 分数达到 90 分的学生和 189 分 PAT 分数达到 95 分的学生可以额外进入名单。第二批就只剩下 175、189 两个分数的学生各一名可以进入名单了。最终一共 8 人进入推荐名单。

### 题目分析： ###

> 只考虑得分不低于 175 分的学生；  
> 一共接受 K 批次的推荐名单；  
> 同一批推荐名单上的学生的成绩原则上应严格递增；  
> 如果有的学生天梯赛成绩虽然与前一个人相同，但其参加过 PAT 考试，且成绩达到了该企业的面试分数线，则也可以接受。

主要从最后一句可以分析出：（要进行简化，不然会超时）

**只要这个学生的天梯赛成绩与面试成绩达到要求就一定可以被选上**

故我们可以将这些学生直接记为通过而不用去进行接下来的计算就将答案累加起来即可

接下来可以把剩余的学生进行计算，先进行排序，

在剩余的这些学生里一批对同一个分数的人，只能选取其中一个人走，那么k批最多选k个人走，但是剩下的几个人中同一分数的可能不够k个人，所以要在k与剩下的同分数的人中去最小

**min(k,kk);**

kk代表剩下的同一分数的人

**kk的初始值为1**

所取的最小值就是可以再加进去的人数

Ps：我最开始写的while每批次都不断进行循环加人，这样写会超时，故用上面的写法可以避免超时，一次循环即可

#include<bits/stdc++.h>
    using namespace std;
    const int N=1e6+10; 
    int n,k,s,ans,num;
    struct node
    {
    	int tts,pat;//天梯赛，PAT，这个人彻底通过 
    }a[N],b[N];
    bool cmp(node a,node b)
    {
    	if(a.tts!=b.tts)
    	return a.tts>b.tts;
    	else
    	return a.pat<b.pat;
    }
    int main()
    {
    	cin>>n>>k>>s;
    	for(int i=1;i<=n;i++)
    	{
    		cin>>a[i].tts>>a[i].pat;
    		if(a[i].tts>=175&&a[i].pat<s)
    		{
    			num++;
    			b[num].tts=a[i].tts;
    			b[num].pat=a[i].pat;
    		}
    		else if(a[i].tts>=175&&a[i].pat>=s)
    		{
    			ans++;
    		}
    	}
    	sort(b+1,b+1+num,cmp);
    	for(int i=1;i<=num;i++)
    	{
    		int kp=b[i].tts;
    		int kk=1;
    		while(kp==b[i+1].tts)
    		{
    			kk++;
    			i++;
    		}
    		ans+=min(k,kk);
    	}	
    	cout<<ans;
    	return 0;
    }

[icon-default.png_t_N5K3]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/7ce3010a81a64cb6bd5f567b613cf2cc.png
[https_pintia.cn_problem-sets_994805046380707840_exam_problems_1518582000729911296_icon-default.png_t_N5K3_https_pintia.cn_problem-sets_994805046380707840_exam_problems_1518582000729911296]: https://pintia.cn/problem-sets/994805046380707840/exam/problems/1518582000729911296