程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> bnu 34982 Beautiful Garden

bnu 34982 Beautiful Garden

編輯：C++入門知識

bnu 34982 Beautiful Garden

Beautiful Garden

There are n trees planted in lxhgww's garden. You can assume that these trees are planted along the X-axis, and the coordinate of ith tree is xi. But in recent days, lxhgww wants to move some of the trees to make them look more beautiful. lxhgww will recognize the trees as beautiful if and only if the distance between any adjacent trees is the same. Now, lxhgww wants to know what is the minimum number of trees he need to move. Just to be clear, after moving, there should still be n trees in the X-axis.

Input

The first line of the input contains a single integer T, which is the number of test cases. For each case,

The first line contains an integers number n (1 ≤ n ≤ 40), representing the number of trees lxhgww planted;

The second line contains n integers numbers, the ith number represents xi. (-1000000000 ≤ xi ≤ 1000000000)

Output

For each case, first output the case number as "Case #x: ", and x is the case number. Then output a single number, representing the minimum number of trees lxhgww needs to move.

Sample Input

1
4
1 3 6 7

Sample Output

Case #1: 1

Source

2014 ACM-ICPC Beijing Invitational Programming Contest

題解及代碼：

#include 
#include 
#include 
#include 
using namespace std;
mapMap;

int main () {

    int cas,n;
    long long s[45];
    scanf("%d",&cas);
    for(int ca=1;ca<=cas;ca++)
    {
        scanf("%d",&n);
        Map.clear();
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&s[i]);
            if(Map.find(s[i])==Map.end()) Map[s[i]]=1;
            else Map[s[i]]++;
        }
        if(n==2)
        {
            printf("Case #%d: 0\n",ca);
            continue;
        }

        int ans=50;
        for(int i=1;i<=n;i++)
        {
            ans=min(ans,n-Map[s[i]]);
            for(int j=i+1;j<=n;j++)
            {
                long long dis=(s[i]>s[j])?s[i]-s[j]:s[j]-s[i];
                if(dis==0) continue;
                for(int k=0;k<=n-2;k++)
                {
                    if(dis%(k+1)) continue;
                    long long  di=dis/(k+1);
                    long long c=min(s[i],s[j]);
                    int cnt=0;
                    for(int x=0;x<=k+1;x++)
                    {
                        if(Map.find(c)!=Map.end()) cnt++;
                        c+=di;
                    }
                    ans=min(ans,n-cnt);
                }
            }
        }
        printf("Case #%d: %d\n",ca,ans);
    }
    return 0;
}
/*
這道題，因為n比較小而且至少有兩棵樹是不用動的，我們直接暴力枚舉起點以及其後另外一點，
然後枚舉兩棵樹之間樹的數目，算好間距，模擬即可。

比賽的時候還在糾結，如果選定的起點在最優的情況下不是起點怎麼辦？後來發現自己多慮了。
假設我們選定的起點是i，另外一點是j（j>i），如果存在上述最優的情況起點在i左側假設為k（k