算法-每天一道题（23）-数组处理

一场考试包含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++有规范版

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Soluction
{
public:
	void getResult()
	{
		int n;
		while (cin >> n)
		{
			vector<int> v(n);
			this->getVector(v, n);
			cout << this->getCount(v, n) << endl;
			v.clear();
		}
	}

	void getVector(vector<int> &v, const int n)
	{
		for (int i = 0; i<n; i++)
			cin >> v[i];
		sort(v.begin(), v.end());
	}

	void checkGroup(vector<int> &v, int &befor, int &after)
	{
		if ((v[v.size() - 1] - v[v.size() - 2] <= 10) && (v[v.size() - 2] - v[v.size() - 3] <= 10))
		{
			for (int i = 0; i<3; i++)
				v.pop_back();
			befor = v.size() - 2;
			after = v.size() - 1;
		}
	}

	int getCount(vector<int> v, int n)
	{
		int befor = v.size() - 2;
		int after = v.size() - 1;
		int all_count = 0;
		while (true)
		{
			/*---------------annotate------------------*/
			cout << "The vector = ";
			for (int i = 0; i < v.size(); i++)
				cout << v[i] << " ";
			cout << endl;
			/*------------------------------------------*/
			if (v.size() >= 3)
				checkGroup(v, befor, after);
			if (v.empty())
				break;
			if (befor < 0)
			{
				v.insert(v.begin(), v[0] - 10);
				befor++;
				after++;
				all_count++;
			}
			else if ((v[after] - v[befor]) > 10)
			{
				v.insert(v.begin() + after, v[after] - 10);
				all_count++;
			}
			else
			{
				befor--;
				after--;
			}
		}
		return all_count;
	}
};

int main()
{
	Soluction *s = new Soluction();
	s->getResult();
	return 0;
}

/*
解题思路：

先排序，从后往前删，三个为一组地删。
把每次insert的次数记下。
比较恶心的是，往前删的时候，遇见只有两个数，或者只有一个数的时候，需要怎么办。
简单明了的方法是，每次都检查一下后三个数是否可以删。如果可以删，再把before和after都重置一下。
然后就只需要不停的insert就可以了。
*/

C++混乱版

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int main()
{
    int n;
    while (cin >> n)
    {
        vector<int> v(n);
        for (int i = 0; i<n; i++)
            cin >> v[i];
        sort(v.begin(), v.end());

        int befor = v.size() - 2;
        int after = v.size() - 1;
        int count = 0;
        int all_count = 0;
        while (true)
        {
            if (v.empty())
                break;
            if (befor < 0)
            {
                v.insert(v.begin(), v[0] - 10);
                befor++;
                after++;
                all_count++;
                count++;
            }
            else if ((v[after] - v[befor]) > 10)
            {
                v.insert(v.begin() + befor + 1, v[after] - 10);
                count++;
                all_count++;
            }
            else
            {
                befor--;
                after--;
                count++;
            }

            if (count >= 2)
            {
                if (v.size() >= 3)
                    for (int i = 0; i < 3; i++)
                        v.pop_back();
                else
                    continue;
                befor = v.size() - 2;
                after = v.size() - 1;
                count = 0;
            }
        }
        cout << all_count << endl;
    }
    return 0;
}