本文主要是介绍备战 清华大学 上机编程考试-冲刺前50%,倒数第6天,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
真题训练:
T1:舞蹈团 - 排序+滑动窗口
生活在在外星球X上的小Z想要找一些小朋友组成一个舞蹈团,于是他在网上发布了信息,一共有 \(n\) 个人报名面试。面试必须按照报名的顺序依次进行。小Z可以选择在面试完若干小朋友以后,在所有已经面试过的小朋友中进行任意顺序的挑选,以组合成一个舞蹈团。虽然说是小朋友,但是外星球X上的生态环境和地球上的不太一样,这些小朋友的身高可能相差很大。小Z希望组建的这个舞蹈团要求至少有 \(m\) 个小朋友,并且这些小朋友的最高身高和最低身高之差不能超过 \(k\) 个长度单位。现在知道了这些小朋友的身高信息,问小Z至少要面试多少小朋友才能在已经面试过的小朋友中选出不少于 \(m\) 个组成舞蹈团。
链接:REKCARC-TSC-UHT/大三小学期/保研考试/推研题目/THUPUB2017/statements/tuoj/day1/interview.md at master · PKUanonym/REKCARC-TSC-UHT (github.com)
解:
(在“轩轩”前辈的代码上,做了一些优化)
#include<iostream>
#include<vector>
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<string>using namespace std;//定义学生类
struct student
{int id;int h;
};//重载小于符号:
bool operator <(const student& a,const student& b)
{return a.h < b.h;
}//利用 插入排序 进行改进:
//这一次不再调用sort(vec.begin()+1,vec.begin()+m+i+1)
//但是,要实现相同的功能,只是内部实现必须更加高效
//前m-1个调用sort
//后面就调用mySort
void mySort(vector<student> &vec,int m,int i)
{//vec[1] - vec[m+i-1]都是有序的,只要把vec[m+i]放到合适的位置即可:student tmp = vec[m+i];for(int u = m+i-1 ; u>=1 ; u--){if(vec[u] < tmp){//把tmp放到u+1的位置,把u+1 - m+i-1后移1个位置for(int w = m+i-1; w>=u+1 ;w--){vec[w+1] = vec[w];}vec[u+1] = tmp;break;}else if(u == 1 && vec[u].h > tmp.h){//tmp需要放到第一个位置for(int w = m+i-1 ; w>=1;w--){vec[w+1] = vec[w];}vec[1] = tmp;break;}}
}int main()
{//处理输入:int n,m,k;cin>>n>>m>>k;//输入n个小朋友的身高vector<student> vec(n+1);for(int i = 1; i<=n;i++){cin>>vec[i].h;vec[i].id = i; //id都是从1开始的}//从1到n一次遍历,选出 m个朋友, 最高 - 最矮 <= k//输出面试完 atleast 个人://其实这个问题挺难的,因为,你要 选择合适的 m个人int atleast = 0; //至少需要的面试的人数//--大概按照“轩轩”前辈的思路进行求解,但是有所改进sort(vec.begin()+1,vec.begin()+m);for(int i = 0 ;i<= n-m;i++){mySort(vec, m,i) ; //sort(vec.begin()+1,vec.begin()+m+i+1); //sort是左闭右开的for(int j = 1;j<=i+1 ; j++) //滑动窗口{//检查是否满足 最大 最小的 差值 <=k的条件:if(vec[j+m-1].h - vec[j].h <=k){//搞定:cout<<m+i<<endl;return 0;}}}cout<<"impossible"<<endl;//真的很像一个dp动态规划://那么,怎么设置初始状态 和 转移方程呢?//状态dp[i] : 至少面试了i人,才能获取到的满足 max - min <= k 的最大人数//初始状态dp[1] = 1//转移方程://思路二: 每次加入一个人,都进行一次sort排序://又有一些滑动窗口的感觉//我先写一个朴素的方法://反正只是需要每次检查第i个,只要知道加入了第i个//是否满足即可://这种朴素的方法,存在可以改进的地方,是否可以将前一次的信息利用起来//其中一种做法是,直接暴力://从头m个,m+1个,m+2个,一直到m+(n-m)个,//每次进行sort排序,从头开始 检查, 窗口大小为m的是否满足//虽然“轩轩的代码挺不错的”,但是//我觉得有一点可以改进,就是哪个for(int y = j,y<j+m;y++)找最大id这个循环//是不需要的,因为随着i的逐渐增大,tall一定是(m-1),m,m+1//“否则,我干嘛还要加入后一个元素”——请仔细思考这句话//还有一个可以改进的点,其实不必要每次全部sort,写一个 插入排序或许更优//毕竟前面都是排序好的 return 0 ;
}
这篇关于备战 清华大学 上机编程考试-冲刺前50%,倒数第6天的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!