放学辣[简单版]

链接：登录—专业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;
}