打个酱油~

挽救一下不要沉了

完工。可惜到现在没有进一步的题目描述，否则我也许能写的更高效一些。

也没有更多的测试数据，欢迎各位自己制作数据进行测试。

也没有精确的格式描述，所以我自己制定了一个输入输出格式。

输入：单组样例，第一行一个数值n，接下来n个数值（>0）。
输出：一个数值，最少分组数。

在正式的输出之间下面的代码还加了一段测试输出（由注释标识代码部分），用来输出一个最少分组方案。

#include<stdio.h>
#include<stdlib.h>

typedef struct path{ int node; struct path * pre; }PATH;
typedef struct{ int left, right; }GRAGH;

int cmp(const void * a, const void * b)
{
    return *(int *)a - *(int *)b;
}

int cal(int * a, int n)
{
    GRAGH * g;
    PATH * p, * tp;
    int * m, * s, pn, c = 0, i, j, k, t;

    g = (GRAGH *)malloc(n * (sizeof(GRAGH) + sizeof(PATH) + sizeof(int) * 2));
    p = (PATH *)&g[n];
    m = (int *)&p[n];
    s = (int *)&m[n];
    qsort(a, n, sizeof(int), cmp);
    for(i = 0; i < n; i++)
    {
        for(j = -1, k = i - 1; j < k; a[t] > a[i] / 3 ? (k = t - 1) : (j = t))
            t = (j + k + 1) >> 1;
        g[i].left = k;
        for(j = i + 1, k = n; j < k; a[t] < a[i] * 3 ? (j = t + 1) : (k = t))
            t = (j + k) >> 1;
        g[i].right = j;
    }
    for(i = 0; i < n; m[i++] = -1);
    p[0].pre = NULL;
    
    for(i = 0; i < n; i++)
    {
        if(m[i] != -1) continue;
        p[0].node = i;
        pn = 1;
        for(j = 0; j < n; s[j++] = 0);
        s[i] = 1;
        for(j = 0; j < pn; j++)
        {
            for(k = g[p[j].node].left; k >= 0 && m[k] != -1; k--)
            {
                if(s[k]) continue;
                p[pn].node = m[k];
                p[pn++].pre = &p[j];
                s[k] = s[m[k]] = 1;
            }
            if(k >= 0) break;
            for(k = g[p[j].node].right; k < n && m[k] != -1; k++)
            {
                if(s[k]) continue;
                p[pn].node = m[k];
                p[pn++].pre = &p[j];
                s[k] = s[m[k]] = 1;
            }
            if(k < n) break;
        }
        if(j < pn)
        for(c++, tp = &p[j]; tp; tp = tp->pre)
        {
            m[k] = tp->node;
            t = m[tp->node];
            m[tp->node] = k;
            k = t;
        }
    }
    
/*output for test*/
    for(i = 0; i < n; i++)
    {
        if(m[i] == i) continue;
        if(m[i] == -1){ printf("(%d)\n", a[i]); continue;}
        printf("(%d,%d)\n", a[i], a[m[i]]);
        m[m[i]] = m[i];
        m[i] = i;
    }
/*test end*/

    free(g);
    return n - c;
}

int main()
{
    int * a, n, i;
    scanf("%d", &n);
    a = (int *)malloc(n * sizeof(int));
    for(i = 0; i < n; scanf("%d", &a[i++]));
    printf("%d\n", cal(a, n));
    free(a);
    return 0;
}

好冷清的一天。大周末的都玩去了，还是在回家的火车上？

你都叫我们小朋友，周末能不玩会么？

你这道简单的题搞这么复杂，有何用意？
试想一下，一列拍好序的数，A1，A2，A3......B1，B2，B3,B4.
如果如果A2能匹配最小的数B2，那么他有什么理由去配B3？占用下一个有可能匹配的资源？假设A3能匹配B3，而不能匹配B4，这就少了一组匹配。
题目说三倍或者大于3倍，没说是3个倍数，最小匹配法就是这题的解题思路。

2组数
1 3 9 27
1 3 4 9

是我想错了。

无知者无畏

是我想错了，随便你怎么说。我认。