D - Exam Results Gym - 102769E

题目链接
题意:
1:给定一个数n和一个百分比p(%为单位)
2:输入n行,每一行有两个数据,一个是当前人的最高成绩,一个是最低成绩,且只能得这两个成绩中得一个
3:只有大于最高成绩的p%是才算及格
4:问最多有多少人及格

题解:用两个优先队列,一个是所有的人,另一个是不及格的,然后再遍历将每一个最大值转换成小值的时候的有多少人可以及格,最终找那个最大值即可.具体看代码

下面是AC代码:

#include <bits/stdc++.h>
#include<iostream>
using namespace std;
#define int long long
const int N = 5e5 + 10;
struct node
{int now;int a, b, id;bool operator<(const node &A) const{if(A.now==now) return A.b > b;return (A.now > now);//按照now值排序}
} f[N];
int vis[N];
priority_queue<node> que;//所有人的优先队列
priority_queue<node> que1;//不及格人数的优先队列
signed main()
{int t;cin >> t;int Case = 0;while (t--){while(que.size())que.pop();while(que1.size())que1.pop();//记得清空数组printf("Case #%lld: ",++Case);int n,jgl;scanf("%lld%lld", &n, &jgl);for(int i=0;i<=n;i++) vis[i]=0;//标记记得清零int fs = 0;int minn=-1;for (int i = 1; i <= n; i++){f[i].id = i;scanf("%lld%lld", &f[i].a, &f[i].b);f[i].a *= 100;f[i].b *= 100;f[i].now = f[i].a;que.push(f[i]);//将所有人的最大值放进这个代码里}int pp = que.top().now * jgl / 100;//算出初始值的最大值int ans = 0;for(int i = 1;i<=n;i++){if(f[i].now < pp)que1.push(f[i]);elseans++;//算出初始的及格人数}while(que.size()){node p = que.top();//取出当前的最大值que.pop();int fsx = p.now * jgl / 100;//算出分数线vis[p.id] ++;//记录使用过的次数,大于两次直接break不然可能某一个人的最小值和最大值都能做最大值,这样就就会死循环node nowp = p;nowp.now = nowp.b;que.push(nowp);//now值变为b后放入队列while(que1.size()) //不及格{node p1 = que1.top();if(fsx > p1.now)break;que1.pop();//及格的一定要pop掉不能放回原来的que,因为放到原来的que后原来的que就乱了}ans = max(ans,n - (int)que1.size());//每次找出一个最大值if(nowp.now<fsx) que1.push(nowp);//这个一定要放在while循环后面if(vis[p.id]>=2) break;//访问超过两次直接break}cout << ans << endl;}return 0;
}

下面是AC的第二种写法:(本质上是一样的,具体看代码即可)

#include <bits/stdc++.h>
#include<iostream>
using namespace std;
#define int long long
const int N = 5e5 + 10;
struct node
{int now;int a, b, id;bool operator<(const node &A) const{if(A.now==now) return A.b > b;return (A.now > now);//按照now值排序}
} f[N];
int vis[N];
priority_queue<node> que;//所有人的优先队列
priority_queue<node> que1;//不及格人数的优先队列
signed main()
{int t;cin >> t;int Case = 0;while (t--){while(que.size())que.pop();while(que1.size())que1.pop();//记得清空数组printf("Case #%lld: ",++Case);int n,jgl;scanf("%lld%lld", &n, &jgl);for(int i=0;i<=n;i++) vis[i]=0;//标记记得清零int fs = 0;int minn=-1;for (int i = 1; i <= n; i++){f[i].id = i;scanf("%lld%lld", &f[i].a, &f[i].b);f[i].a *= 100;f[i].b *= 100;f[i].now = f[i].a;que.push(f[i]);//将所有人的最大值放进这个代码里}int pp = que.top().now * jgl / 100;//算出初始值的最大值int ans = 0;for(int i = 1;i<=n;i++){if(f[i].now < pp)que1.push(f[i]);elseans++;//算出初始的及格人数}//这个整体的思路就是在开始就找交换然后找最小值while(que.size()){node p = que.top();//取出当前的最大值que.pop();node t1=p;t1.now=p.b;que.push(t1);p=que.top();int fsx = p.now * jgl / 100;//算出分数线vis[p.id] ++;//记录使用过的次数,大于两次直接break不然可能某一个人的最小值和最大值都能做最大值,这样就就会死循环if(t1.now<fsx) que1.push(t1);while(que1.size()) //不及格{node p1 = que1.top();if(fsx > p1.now)break;que1.pop();//及格的直接出去即可}ans = max(ans,n - (int)que1.size());//每次找出一个最大值if(vis[p.id]>=2) break;//访问超过两次直接break}cout << ans << endl;}return 0;
}

这个题改了很长的时间,本来以为是思路问题,后来找到样例后发现是一些细节没有注意到,截个图纪念一下吧:

下面是WA2的代码:

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 10;
struct node
{int now;int a, b, id;bool operator<(const node &A) const{if(A.now==now) return A.b > b;return (A.now > now);}
} f[N];int vis[N];
priority_queue<node> que;
priority_queue<node> que1;
signed main()
{int t;cin >> t;int Case = 0;while (t--){while(que.size())que.pop();while(que1.size())que1.pop();printf("Case #%lld: ",++Case);int n,jgl;scanf("%lld%lld", &n, &jgl);for(int i=0;i<=n;i++) vis[i]=0;int fs = 0;for (int i = 1; i <= n; i++){f[i].id = i;scanf("%lld%lld", &f[i].a, &f[i].b);f[i].a *= 100;f[i].b *= 100;f[i].now = f[i].a;que.push(f[i]);}int pp = que.top().now * jgl / 100;int ans = 0;for(int i = 1;i<=n;i++){if(f[i].now < pp)que1.push(f[i]);elseans++;}while(que.size()){node p = que.top();que.pop();node nowp = p;nowp.now = nowp.b;int fsx = p.now * jgl / 100;if(nowp.b<fsx) que1.push(nowp);else que.push(nowp);vis[p.id] ++;while(que1.size()) //不及格{node p1 = que1.top();if(fsx > p1.now)break;que1.pop();}ans = max(ans,n - (int)que1.size());if(vis[p.id]>=2) break;//访问超过两次直接break}cout << ans << endl;}return 0;
}

下面是纠错的样例:
1
5 100
100 2
1 1
2 1
2 1
2 1
答案是:4