排序+贪心,代码里都有注释,逻辑很清楚
头条校招
http://www.nowcoder.com/questionTerminal/57cf0b1050834901933e9b48daafbb9a
#include<iostream> #include<vector> #include<algorithm> //sort using namespace std; void solve(vector<int> & vec){ sort(vec.begin(),vec.end()); //升序排序 int n=vec.size(); int ans=0; for(int i=0;i<n;){ if(n-1-i+1>=3){ //还剩至少三个题 if(vec[i+1]-vec[i]<=10&&vec[i+2]-vec[i+1]<=10){ //三个题可以直接构成一场考试 i+=3; }else if(vec[i+1]-vec[i]<=10&&vec[i+2]-vec[i+1]>10){ //第一二个题满足条件,但是第二三个题目不满足,则在一二题后加入一个新题 i+=2; ans++; }else if(vec[i+1]-vec[i]>10){ //第一个题就不满足条件,需要在第一个题后加入两个新题 ++i; ans+=2; } }else if(n-1-i+1==2){//还剩两个题目 if(vec[i+1]-vec[i]<=10){ //这两个题满足条件,再加一题即可 i+=2; ans++; }else if(vec[i+1]-vec[i]>10&&vec[i+1]-vec[i]<20){ //这两个题中间可以插入一题,其实可以和上一个if合并 i+=2; ans++; }else{ //这两个题难度差距太大,中间插入一题也无法满足条件,因此需要加入4个新题 i+=2; ans+=4; } }else if(n-1-i+1==1){//还剩一个题目 i++; ans+=2; } }// end for cout<<ans<<endl; } int main(){ int n; while(cin>>n){ vector<int> vec(n,0); for(int i=0;i<n;++i) cin>>vec[i]; solve(vec); } return 0; }