笔试刷题-头条2018-07-03

题目描述：

/**
头条的2017校招开始了！
为了这次校招，我们组织了一个规模宏大的出题团队，
每个出题人都出了一些有趣的题目，
而我们现在想把这些题目组合成若干场考试出来，
在选题之前，我们对题目进行了盲审，并定出了每道题的难度系统。
一场考试包含3道开放性题目，假设他们的难度从小到大分别为a,b,c，
我们希望这3道题能满足下列条件：
a<=b<=c
b-a<=10
c-b<=10
所有出题人一共出了n道开放性题目。
现在我们想把这n道题分布到若干场考试中
（1场或多场，每道题都必须使用且只能用一次），
然而由于上述条件的限制，
可能有一些考试没法凑够3道题，
因此出题人就需要多出一些适当难度的题目来让每场考试都达到要求，
然而我们出题已经出得很累了，
你能计算出我们最少还需要再出几道题吗？
输入描述:
输入的第一行包含一个整数n，表示目前已经出好的题目数量。
第二行给出每道题目的难度系数d1,d2,...,dn。
数据范围
对于30%的数据，1 ≤ n,di ≤ 5;
对于100%的数据，1 ≤ n ≤ 10^5,1 ≤ di ≤ 100。
在样例中，
一种可行的方案是添加2个难度分别为20和50的题目，
这样可以组合成两场考试：（20 20 23）和（35,40,50）。
输出描述:
输出只包括一行，即所求的答案。
输入例子1:
4
20 35 23 40
输出例子1:
2
*/

思路如下：

把难度从小到大排序，然后用一个标记题目是否用于考试
然后对于三个连续的题目
按遍历顺序marked
i i+1 i+2
设间隔长度为distMax
若difficulty简称diff
diff[i+2]<=diff[i]+2diffMax
那么这三个直接放一组
否则diff[i+2]>diff[i]+2diffMax
若diff[i+1]<=diff[i]+2*diffMax
那么在i+1之后要添加一个题目使得i i+1组成一个三元组
或者在i与i+1之添加一个三元组
否则
为i添加2个题目组成一个三元组
最后还剩下0 1 2个最后两题没有处理要再处理一下即可

代码如下：

#include<stdio.h>
#include<iostream>
#include<algorithm>
 
#define MAX_N 100005
#define MAX_DIST 10
 
using namespace std;
 
bool marked[MAX_N];
int diff[MAX_N];
 
int main()
{
    int N, acc=0;
    scanf("%d", &N);
    for(int i=0; i<N; i++){
        scanf("%d", diff+i);
    }
    sort(diff, diff+N);
    for(int i=0; i+2<N; i++)
    {
        if(marked[i])
            continue;
        if(diff[i+2]<=diff[i]+2*MAX_DIST){
            marked[i]=true;
            marked[i+1]=true;
            marked[i+2]=true;
        }
        else{
            if(diff[i+1]<=diff[i]+2*MAX_DIST){
                marked[i]=true;
                marked[i+1]=true;
                acc+=1;
            }
            else{
                marked[i]=true;
                acc+=2;
            }
        }
    }
    if(N<1)
        return -1;
    if(N==1)
        acc+=2;
    else if(!marked[N-2]){//隐含marked[N-1]=false
        if(diff[N-1]>diff[N-2]+2*MAX_DIST)
            acc+=4;
        else
            acc+=1;
    }
    else if(!marked[N-1]){
        acc+=2;
    }
    printf("%d", acc);
    return 0;
}