新开发网站互联网推广加盟
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
题目描述
本题和 D 题的唯一区别是 NNN 的范围。
校园里目前有 NNN 名学生，这些学生属于 MMM 个班级。第 iii（i=1,2,...,Ni = 1,2,...,Ni=1,2,...,N）个人属于第 AiA_iAi 个班级。突然，放学铃声响起，你还没来得及思索，就已经有 KKK 名学生已经冲出了学校。然而，由于某班级的老师还在拖堂，可以确定这个班级目前还没有任何学生离校。现在请你求出，假设恰好只有班级 jjj（j=1,2,...,Mj = 1,2,...,Mj=1,2,...,M）的老师还在拖堂，在剩下的未拖堂的班级中，还留在学校的人数最多的班级的最少的可能人数是多少。
输入描述:
第一行三个正整数 NNN（1≤N≤1021 \leq N\leq 10^21≤N≤102），MMM（1≤M≤N1 \leq M\leq N1≤M≤N），KKK（1≤K≤N1 \leq K\leq N1≤K≤N）含义如上所述。
第二行 NNN 个正整数 AiA_iAi（1≤Ai≤M1 \leq A_i\leq M1≤Ai≤M），含义如上所述。
输出描述:
M 个整数，第 i 个整数表示恰好只有班级 i 的老师还在拖堂，在剩下的未拖堂的班级中，还留在学校的人数最多的班级的最少的可能人数是多少。如果班级 i 拖堂就不可能有 K名学生冲出学校，则输出 -1。
示例1
输入
6 3 3
3 1 2 3 3 2输出
1 1 0示例2
输入
6 3 4
3 1 2 3 3 2输出
1 0 -1其实这个题完全是因为思路被带偏了。前面有一道差不多的题目，我用的map加上匿名函数排序过的（中途sort忘记加cmp参数WA了一发），然后这一题也想这样做，只是每次那一个earse了当前班级的副本去运算，本来这个思路是对的，但是后面到具体的放人的环节模拟错了，我是将所有的班级当成整体看，正确解法应当要用优先队列维护每个班级的人数，从最多的人的合法班级里面放一个走，然后维护队列
先放我的错误解法吧，特例都对了，就是不知道错哪了
#include<iostream>
#include<map>
#include<algorithm>
using namespace std;
// #define DEBUG true
int n,m,k;
// 拖堂的班级的人数
int normalNums=0;//调用可以进行重定向
void initRedict(){#ifdef DEBUGcout<<"执行重定向"<<endl; //重定向输入 freopen("../redict/demo/demo_in.txt","r",stdin); //重定向输出 覆写
// freopen("../redict/demo/demo_out.txt","w",stdout); #endif
}
// 调用可以取消重定向
void breakEnd(){#ifdef DEBUGfclose(stdin);fclose(stdout); #endif
}bool cmp(const pair<int,int>& a,const pair<int,int>& b){return a.second<b.second;
}int judge(int nums){if (nums&1) return 1;return 0;
}
void solved(map<int,int> mymap){
// 自由班级最多人数 map<int,int>::iterator iter=max_element(mymap.begin(),mymap.end(),cmp);int maxValue=iter->second;// 统计第二大的班级人数 mymap.erase(iter->first);int secondMaxValue= max_element(mymap.begin(),mymap.end(),cmp)->second;// 获取最小int minValue= min_element(mymap.begin(),mymap.end(),cmp)->second;
// cout<<maxValue<<" 打水印"<<endl;int nowTotalNums=n-normalNums;if (maxValue-secondMaxValue>k){cout<<maxValue-secondMaxValue;}else if (nowTotalNums>=k){
// secondMaxValue不够大
// cout<<"打印k a b"<<k<<" "<<maxValue<<" "<<secondMaxValue<<" "<<endl;
// if (nowTotalNums>k) cout<<"1"; cout<<secondMaxValue-(k-(maxValue-secondMaxValue))/2;
// if (secondMaxValue-(k-(maxValue-secondMaxValue))/2>minValue){
// cout<<secondMaxValue-(k-(maxValue-secondMaxValue))/2;
// }
// else{
// cout<<minValue;
// }}else{cout<<"-1";}cout<<" ";
// // 又没有超过其他小班的人数和
// if (k<=nowTotalNums-maxValue){
// cout<< maxValue-normalNums;
// }
// else{
// cout<<n-k-normalNums;
// }}
map<int,int> mymap;
int main(){initRedict();cin>>n>>m>>k;for(int i=0;i<n;i++){int nums;cin>>nums;mymap[nums]++;}for(int i=1;i<=m;i++){map<int,int> tempMap=mymap;normalNums=tempMap[i]; tempMap.erase(i);solved(tempMap);}return 0;
} 下面是合理的思路，就是简单考察对数据结构的运用，而不是算法考察！！！
#include<iostream>
#include<map>
#include<algorithm>
#include<queue>
using namespace std;
//#define DEBUG true
int n,m,k;
// 拖堂的班级的人数
int normalNums=0;//调用可以进行重定向
void initRedict(){#ifdef DEBUGcout<<"执行重定向"<<endl; //重定向输入 freopen("../redict/demo/demo_in.txt","r",stdin); //重定向输出 覆写
// freopen("../redict/demo/demo_out.txt","w",stdout); #endif
}
// 调用可以取消重定向
void breakEnd(){#ifdef DEBUGfclose(stdin);fclose(stdout); #endif
}map<int,int> mymap;
int main(){initRedict();cin>>n>>m>>k;for(int i=0;i<n;i++){int nums;cin>>nums;mymap[nums]++;}bool flag=false;for(int i=1;i<=m;i++){
// if (mymap[i]+k>n){if (flag) cout<<" ";cout<<"-1";flag=true;continue;}
// 我们需要一个升序的结构 priority_queue<int ,vector<int>,less<int> >myqueue; // 开始统计 使用优先队列即可for(int j=1;j<=m;j++){if (i-j){myqueue.push(mymap[j]);}} // 开始进行放人 从最多的开始放int coun=k;
// cout<<coun<<endl; while(coun--){int classNums=myqueue.top();myqueue.pop();myqueue.push(classNums-1);} if (flag) cout<<" ";cout<<myqueue.top();flag=true;}return 0;
}