洛谷 P3137(silver)/bzoj 4412(gold) [USACO16FEB]圆形谷仓Circular Barn题解【贪心】

作者: wjyyy 分类: 解题报告,贪心 发布时间: 2018-07-16 10:18

点击量:12

 

   肥肠好的一道有思维的贪心。

 

题目描述

Being a fan of contemporary architecture, Farmer John has built a new barn in the shape of a perfect circle. Inside, the barn consists of a ring of \(n\) rooms, numbered clockwise from \(1 \ldots n\) around the perimeter of the barn. Each room has doors to its two neighboring rooms, and also a door opening to the exterior of the barn.

 

Farmer John owns \(n\) cows, and he wants exactly one cow to end up in each room in the barn. However, the cows, being slightly confused, line up at haphazard doors, with possibly multiple cows lining up at the same door. Precisely \(c_i\) cows line up outside the door to room \(i\) , so \(\sum c_i=n\).

 

To manage the process of herding the cows so that one cow ends up in each room, Farmer John wants to use the following approach: each cow enters at the door at which she initially lined up, then walks clockwise through the rooms until she reaches a suitable destination. Given that a cow walking through \(d\) doors consumes \(d^2\) energy, please determine the minimum amount of energy needed to distribute the cows so one ends up in each room.

 

给定一个环长为\(n\)的环,环上每个点上有\(a_i\)只牛,每只牛可以在环上顺时针移动,代价为移动距离的平方,问使环上每个节点上都有一只牛的代价是多少。

 

输入输出格式

输入格式:

The first line of input contains \(n\). Each of the remainin \(n\) lines contain \(c_1\ldots c_n\).

 

输出格式:

Please write out the minimum amount of energy consumed by the cows.

 

输入输出样例

输入样例#1:
10
1
0
0
2
0
0
1
2
2
2
输出样例#1:
33

题解:

1.<silver>,\(3\le n\le 1,000\)

   对于\(n\le 1,000\)的数据,是可以\(O(n^2)\)水过的。如果这个题不成环,根据贪心,奶牛如果朝顺时针走,会走到当前右数第一个0处,因为如果奶牛的分布是”2 1 0″,则如果让1号位的奶牛直接去3号位,花费为4;如果让2号位奶牛去3号位,让1号位奶牛补到2号位,花费为2。因为根据完全平方公式/基本不等式:\((a+b)^2=a^2+b^2+2ab\ge a^2+b^2\),所以我们从右到左枚举每一头牛,一旦发现最右边有0,就去补。如果到了最后1号位没有奶牛,说明这种状态不合法,因为后面一定有谷仓堆积了2个或以上的奶牛。

 

   不过这是一个环,我们就可以拆环为链,枚举链的开头,时间复杂度为\(O(n^2)\)。

 

   那么为什么可以拆链呢?对于最优解的情况,它一定不会出现越界的情况,因为总有奶牛会待在自己原来的位置上,不然如果所有奶牛都动一次,和没动是没有区别的。

 

2.<gold>,\(3\le n\le 100,000\)

   对于100,000的数据来说,\(O(n^2)\)当然是过不了了。我们就要在\(O(n\log n)\)及以内的复杂度中,找出一条最优拆链方法。因为总有奶牛待在自己原来的位置上,所以我们把所有奶牛排个序,不管顺时针方向,让它们直接按原谷仓顺序进入这\(n\)个新谷仓,那这时找出要逆时针走的最远的奶牛来自哪里。我们只需要把这头奶牛的原位置提到最前面,就会发现,如果重新排序,那么所有的奶牛都不会往逆时针走了,因为我们相当于把这个环整体转了几个单位,满足了上述(silver部分)所有奶牛去补当前右数第一个0,且不会出现堆积的情况,也就是保证了做到最后1号位还有奶牛,避免了不合法。

 

   对于样例,我们排序后的p数组是这样的:

a[原数组]    1  0  0  2  0  0  1  2  2  2
p[排序位置]  1  4  4  7  8  8  9  9 10 10
d[逆时针距离]0  2  1  3  3  2  2  1  1  0

   我们找到第一个d最大的数x,把它原来的位置a[x]放到最前面来,就是把环向左平移了a[x]-1个单位,使得每个d都减少a[x]-1,这样一来,就连最大的数都被减少到0了,跑的最远的也被拉回来起点了,那么所有奶牛都只会往顺时针跑或停在原地了。

 

   旋转以后的三个数组

a[现在数组]    1  2  2  2  1  0  0  2  0  0
p[排序位置]    1  2  2  3  3  4  4  5  8  8
d[逆时针距离]  0  0  0 -1 -2 -2 -3 -3 -1 -2

   这时,我们就找到了一个所有奶牛都往顺时针方向跑,并且保证了最终1号位有奶牛的方案。

 

Code:<silver> 48ms [\(O(n^2)\)写的比\(O(n)\)还长/(ㄒoㄒ)/]

#include<cstdio>
int a[1010],b[1010];
int n,ans=123456789;
int init(int x)
{
    for(int i=1;i<=n;i++)
        a[i]=b[(i+x-2)%n+1];
}
void check()
{
    int to[1010];//下一个非0数
    int sum=0,lst=n;
    for(int i=n;i>=1;i--)
        if(a[i]!=0)
        {
            for(int j=lst;j>i;j--)
                to[j]=i;
            lst=i;
        }
    for(int i=lst;i>=1;i--)
        to[i]=0;
    for(int i=n;i>1;i--)
        if(a[i]==0)
        {
            int k=to[i];
            while(k!=0&&a[k]==0)
                k=to[k];
            if(k==0)
            {
                a[1]=0;
                break;
            }
            sum+=(i-k)*(i-k);
            a[k]--;
        }
    if(a[1]==1)
        ans=ans<sum?ans:sum;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    init(1);
    check();
    for(int i=1;i<n;i++)
    {
        init(i+1);
        check();
    }
    printf("%d\n",ans);
    return 0;
}

Code:<gold> 0ms

#include<cstdio>
#include<cstring>
int a[101000];
int p[101000];
int main()
{
    int n,t=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(a[i])
            for(int j=1;j<=a[i];j++)
                p[++t]=i;
    }
    int mx=-1,k;
    for(int i=1;i<=n;i++)
        if(p[i]-i>mx)
        {
            k=p[i];//向左挪几位,不是i
            mx=p[i]-i;
        }
    k--;
    //把不合法的消掉
    for(int i=1;i<=n;i++)
        p[i]=a[(i+k-1)%n+1];
    for(int i=1;i<=n;i++)
        a[i]=p[i];
    t=0;
    for(int i=1;i<=n;i++)
        if(a[i])
            for(int j=1;j<=a[i];j++)
                p[++t]=i;
    long long sum=0;
    for(int i=1;i<=n;i++)
        sum+=(long long)(p[i]-i)*(long long)(p[i]-i);
    printf("%lld\n",sum);
    return 0;
}

说点什么

avatar
  Subscribe  
提醒
/* */