首页 > 代码库 > bnu 34982 Beautiful Garden

bnu 34982 Beautiful Garden

2024-07-17 23:11:28   228人阅读


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 <iostream>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
map<long long,int>Map;

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<i），
那么我们在进行暴力时，以k为起点，j为另一点的情况，已经计算过这种情况了。
所以这样讲，那我们每次枚举i的时候就不需要考虑左侧的树了，每次都是把左侧的树搬到右边来。
还有就是这道题一个比较坑的点：就是一个点上可以种很多树，稍微处理一下就可以了。

转载请注明出处，谢谢。
*/


联系
我们