排序+贪心,代码里都有注释,逻辑很清楚

头条校招

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;
}
全部评论

相关推荐

11-18 09:44
Java
小白也想要offer:简历别放洋屁,搞不还还放错了,当然你投外企除外,以上纯属个人观点
点赞 评论 收藏
分享
点赞 评论 收藏
分享
点赞 评论 收藏
分享
3 收藏 评论
分享
牛客网
牛客企业服务