Note: This article is available in Chinese only. 本文暂无英文版本。
View original
头条校招（今日头条2017秋招真题）
题目描述
头条的2017校招开始了！为了这次校招，我们组织了一个规模宏大的出题团队。每个出题人都出了一些有趣的题目，而我们现在想把这些题目组合成若干场考试出来。在选题之前，我们对题目进行了盲审，并定出了每道题的难度系数。一场考试包含3道开放性题目，假设他们的难度从小到大分别为a, b, c，我们希望这3道题能满足下列条件：
a＜= b＜= c b - a＜= 10 c - b＜= 10
所有出题人一共出了n道开放性题目。现在我们想把这n道题分布到若干场考试中（1场或多场，每道题都必须使用且只能用一次），然而由于上述条件的限制，可能有一些考试没法凑够3道题，因此出题人就需要多出一些适当难度的题目来让每场考试都达到要求。然而我们出题已经出得很累了，你能计算出我们最少还需要再出几道题吗？
输入输入的第一行包含一个整数n，表示目前已经出好的题目数量。 第二行给出每道题目的难度系数 d1, d2, …, dn。 | 样例输入4 20 35 23 40 |
输出输出只包括一行，即所求的答案。 | 样例输出2 |
时间限制C/C++语言：1000MS其它语言：3000MS | 内存限制C/C++语言：65536KB其它语言：589824K |
div2 A的难度…直接贪就好，不给数据范围的都是耍流氓…
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2017年03月30日 星期四 12时55分21秒
4File Name :code/toutiao/1.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31int n;
32vector<int>vec;
33int main()
34{
35 #ifndef ONLINE_JUDGE
36 freopen("code/in.txt","r",stdin);
37 #endif
38 int ans = 0 ;
39 cin>>n;
40 for ( int i = 1 ; i <= n ; i++)
41 {
42 int x;
43 scanf("%d",&x);
44 vec.push_back(x);
45 }
46 sort(vec.begin(),vec.end());
47 int cur = 0 ;
48 for ( int i = 0 ;i < n ; i++)
49 {
50 if (cur==0)
51 {
52 cur++;
53 continue;
54 }
55 if (cur==1)
56 {
57 if (vec[i]-vec[i-1]<=10)
58 {
59 cur++;
60 continue;
61 }
62 if (vec[i]-vec[i-1]>20)
63 {
64 cur+=2;
65 ans+=2;
66 cur%=3;
67 i--;
68 continue;
69 }
70 if (vec[i]-vec[i-1]>10)
71 {
72 cur+=2;
73 cur%=3;
74 ans++;
75 }
76 continue;
77 }
78 if (cur==2)
79 {
80 if (vec[i]-vec[i-1]<=10)
81 {
82 cur++;
83 cur%=3;
84 continue;
85 }
86 else
87 {
88 cur++;
89 ans++;
90 i--;
91 cur%=3;
92 continue;
93 }
94 }
95 }
96 if (cur!=0)
97 ans = ans + 3-cur;
98 cout<<ans<<endl;
99 #ifndef ONLINE_JUDGE
100 fclose(stdin);
101 #endif
102 return 0;
103}