暖色网站模板,wordpress破解key,网站设计需要哪些,专业网站推广的公司链接#xff1a;登录—专业IT笔试面试备考平台_牛客网 来源#xff1a;牛客网
题目描述
本题和 D 题的唯一区别是 NNN 的范围。 校园里目前有 NNN 名学生#xff0c;这些学生属于 MMM 个班级。第 iii#xff08;i1,2,...,Ni 1,2,...,Ni1,2,...,N#xff09;个人属于第…链接登录—专业IT笔试面试备考平台_牛客网 来源牛客网
题目描述
本题和 D 题的唯一区别是 NNN 的范围。 校园里目前有 NNN 名学生这些学生属于 MMM 个班级。第 iiii1,2,...,Ni 1,2,...,Ni1,2,...,N个人属于第 AiA_iAi 个班级。突然放学铃声响起你还没来得及思索就已经有 KKK 名学生已经冲出了学校。然而由于某班级的老师还在拖堂可以确定这个班级目前还没有任何学生离校。现在请你求出假设恰好只有班级 jjjj1,2,...,Mj 1,2,...,Mj1,2,...,M的老师还在拖堂在剩下的未拖堂的班级中还留在学校的人数最多的班级的最少的可能人数是多少。
输入描述:
第一行三个正整数 NNN1≤N≤1021 \leq N\leq 10^21≤N≤102MMM1≤M≤N1 \leq M\leq N1≤M≤NKKK1≤K≤N1 \leq K\leq N1≤K≤N含义如上所述。 第二行 NNN 个正整数 AiA_iAi1≤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了当前班级的副本去运算本来这个思路是对的但是后面到具体的放人的环节模拟错了我是将所有的班级当成整体看正确解法应当要用优先队列维护每个班级的人数从最多的人的合法班级里面放一个走然后维护队列
先放我的错误解法吧特例都对了就是不知道错哪了
#includeiostream
#includemap
#includealgorithm
using namespace std;
// #define DEBUG true
int n,m,k;
// 拖堂的班级的人数
int normalNums0;//调用可以进行重定向
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 pairint,int a,const pairint,int b){return a.secondb.second;
}int judge(int nums){if (nums1) return 1;return 0;
}
void solved(mapint,int mymap){
// 自由班级最多人数 mapint,int::iterator itermax_element(mymap.begin(),mymap.end(),cmp);int maxValueiter-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;
// coutmaxValue 打水印endl;int nowTotalNumsn-normalNums;if (maxValue-secondMaxValuek){coutmaxValue-secondMaxValue;}else if (nowTotalNumsk){
// secondMaxValue不够大
// cout打印k a bk maxValue secondMaxValue endl;
// if (nowTotalNumsk) cout1; coutsecondMaxValue-(k-(maxValue-secondMaxValue))/2;
// if (secondMaxValue-(k-(maxValue-secondMaxValue))/2minValue){
// coutsecondMaxValue-(k-(maxValue-secondMaxValue))/2;
// }
// else{
// coutminValue;
// }}else{cout-1;}cout ;
// // 又没有超过其他小班的人数和
// if (knowTotalNums-maxValue){
// cout maxValue-normalNums;
// }
// else{
// coutn-k-normalNums;
// }}
mapint,int mymap;
int main(){initRedict();cinnmk;for(int i0;in;i){int nums;cinnums;mymap[nums];}for(int i1;im;i){mapint,int tempMapmymap;normalNumstempMap[i]; tempMap.erase(i);solved(tempMap);}return 0;
}
下面是合理的思路就是简单考察对数据结构的运用而不是算法考察
#includeiostream
#includemap
#includealgorithm
#includequeue
using namespace std;
//#define DEBUG true
int n,m,k;
// 拖堂的班级的人数
int normalNums0;//调用可以进行重定向
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
}mapint,int mymap;
int main(){initRedict();cinnmk;for(int i0;in;i){int nums;cinnums;mymap[nums];}bool flagfalse;for(int i1;im;i){
// if (mymap[i]kn){if (flag) cout ;cout-1;flagtrue;continue;}
// 我们需要一个升序的结构 priority_queueint ,vectorint,lessint myqueue; // 开始统计 使用优先队列即可for(int j1;jm;j){if (i-j){myqueue.push(mymap[j]);}} // 开始进行放人 从最多的开始放int counk;
// coutcounendl; while(coun--){int classNumsmyqueue.top();myqueue.pop();myqueue.push(classNums-1);} if (flag) cout ;coutmyqueue.top();flagtrue;}return 0;
}
