【欲張り】[USACO 2016金組]Circular Barn

タイトルの説明

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 nn rooms, numbered clockwise from 1…n1…n around the perimeter of the barn (3≤n≤100,0003≤n≤100,000). Each room has doors to its two neighboring rooms, and also a door opening to the exterior of the barn. Farmer John owns nn 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 cici cows line up outside the door to room ii, so ∑ci=n∑ci=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 dd doors consumes d2d2 energy, please determine the minimum amount of energy needed to distribute the cows so one ends up in each room.

INPUT FORMAT (file cbarn.in):

The first line of input contains nn. Each of the remaining nn lines contain c1…cnc1…cn.

OUTPUT FORMAT (file cbarn.out):

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

SAMPLE INPUT:

10 1 0 0 2 0 0 1 2 2 2

SAMPLE OUTPUT:

33题目大意,给与一个环长为n的环上每点有ai只牛,每只牛可以在环上按时时计回り移动,代价为移动距离的平方,问问环上每節点上都有一只牛的代価是多少

テーマ解析

iとj(j>i)を移動してkとp(p>k)に到達する必要がある場合、i−>kとj−>pを同時に移動する必要がある場合、任意のj=kに対して同様に満足していることがわかります.では、私たちは貪欲に処理して、毎回現在の位置に循環して、もし私たちが現在の位置に出発できる乳牛があれば、必ず出発(より優れている)して、次の列の中で最も遠い距離を投げて、次の1匹を投げて歩き続けることはありません.

コード#コード#

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN = 100000;
int a[MAXN+10], c[MAXN+10];
char ch;
void Read(int &s){
    while((ch=getchar()),ch<'0'||ch>'9');
    s = ch-'0';
    while((ch=getchar()),ch>='0'&&ch<='9')
        s = s*10+ch-'0';
    ungetc(ch, stdin);
}
int main(){
    int n;
    Read(n);
    for(int i=1;i<=n;i++){
        Read(c[i]);
        a[i] = i;
    }
    queue<int> que;
    long long ans = 0;
    for(int i=1;i<=n;i++){
        if(!que.empty()){
            int u = que.front();
            que.pop();
            ans += 1LL*(i-u)*(i-u);
            a[i] = u;
            c[i] ++;
        }
        for(;c[i]>1;c[i]--) que.push(i);
    }
    int tn = n*2;
    for(int i=n+1;i<=tn;i++){
        if(!que.empty()){
            if(c[i-n]){
                que.push(a[i-n]+n);
                ans -= 1LL*(i-n-a[i-n])*(i-n-a[i-n]);
            }
            int u = que.front();
            que.pop();
            ans += 1LL*(i-u)*(i-u);
        }
    }
    printf("%lld
", ans);

    return 0;
}