本文共 3876 字，大约阅读时间需要 12 分钟。

Description

Lethe loves eating chocolates very much. In Lethe’s birthday, her good friend echo brings N boxes to her, and makes the boxes on the circle. Furthermore, echo tells Lethe that there are many chocolates in the boxes, but the total number of chocolates doesn’t exceed N. Also, echo wants Lethe to displace the chocolates in such a way that in each box remains no more than one chocolate. In one move she can shift one chocolate from current box to its neighboring box. (Each box has two neighboring boxes). Can you tell Lethe the minimum number of move to achieve this goal?

Input

There are multi-cases (The total number of cases won’t exceed 20). First line is an integer N(1<=N<=500), the total number of boxes. Then N lines follow, each line includes a number, indicates the number of chocolates in the box.

Output

Output the minimum number of move.

Sample Input

10

1

3

3

0

0

2

0

0

0

0

Sample Output

9

KM算法详情解释请看这篇博客：

题意:

有n个盒子摆成的环，每个盒子里有一定数量的巧克力，巧克力总数小于n，问最少移几步(每步等于把一块巧克力从第i格移动到了i+1或i-1格)，使得每个盒子里巧克力数小于等于1，从第i个盒子移到第j个盒子的最小步数为min( n-abs(i-j), abs(i-j) )。

分析:

如果一个盒子里有5块巧克力,其实我们需要做的就是把这盒子里的4块巧克力分别移到4个空盒子里去.

建立二分图: 左边点集是每一块需要被移动的巧克力, 右边点集是每一个空的盒子. 对于左边第i块巧克力来说,它被移动到右边第j个空盒子的最小距离为X,那么就在左i点与右j点之间加一条X权值的边.

最终我们求得就是该二分图的最小权值匹配.(权值取负数就是最优权值匹配了:)

AC

#include
   
    #include
    
     #include
     
      #define mst(a,b) memset(a,b,sizeof(a))using namespace std;const int maxn=500+8;const int INF=0x3f3f3f3f;int a[maxn],x[maxn],y[maxn];int love[maxn][maxn];   // 记录每个妹子和每个男生的好感度int ex_girl[maxn];      // 每个妹子的期望值int ex_boy[maxn];       // 每个男生的期望值bool vis_girl[maxn];    // 记录每一轮匹配匹配过的女生bool vis_boy[maxn];     // 记录每一轮匹配匹配过的男生int match[maxn];        // 记录每个男生匹配到的妹子 如果没有则为-1int slack[maxn];        // 记录每个汉子如果能被妹子倾心最少还需要多少期望值int n,nx,ny;bool dfs(int girl){
       vis_girl[girl]=true;    for(int boy=1;boy<=ny;++boy){
           if(vis_boy[boy]) continue;        int gap=ex_boy[boy]+ex_girl[girl]-love[girl][boy];        if(gap==0)        {
               vis_boy[boy]=true;            if(match[boy]==-1||dfs(match[boy]))            {
                   match[boy]=girl;                return true;            }        }        else        {
               slack[boy]=min(slack[boy],gap);        }    }    return false;}int KM(){
       mst(match,-1);    mst(ex_boy,0);    for(int i=1;i<=nx;i++)    {
           ex_girl[i]=love[i][0];        for(int j=2;j<=ny;j++)        {
               ex_girl[i]=max(ex_girl[i],love[i][j]);        }    }    for(int i=1;i<=nx;i++)    {
           fill(slack+1,slack+n+1,INF);        while(true)        {
               mst(vis_boy,false);            mst(vis_girl,false);            if(dfs(i)) break;            int d=INF;            for(int j=1;j<=ny;j++)                if(!vis_boy[j]) d=min(d,slack[j]);            for(int j=1;j<=nx;j++)                if(vis_girl[j]) ex_girl[j]-=d;            for(int j=1;j<=ny;j++){
                   if(vis_boy[j])  ex_boy[j]+=d;                else                    slack[j]-=d;            }        }    }    int res=0;    for(int i=1;i<=ny;i++)  //注意这里是ny 不是nx    //match数组定义:记录每个男生匹配到的妹子 如果没有则为-1        if(match[i]!=-1)        res+=love[match[i]][i];    return res;}int main(){
       ios::sync_with_stdio(false);    cin.tie(0);    while(cin>>n)    {
           mst(love,0); //初始化我们二分图的权值边        nx=0;ny=0;  //nx用来记录每个盒子多的巧克力数        			//ny用来记录空盒子数        for(int i=1;i<=n;i++)            cin>>a[i];        for(int i=1;i<=n;i++)        {
               while(a[i]>1)     //当前盒子巧克力总数大于1            {
                   x[++nx]=i;    //记录当前多的一个巧克力所在位置  ++nx                a[i]--;       //当前盒子的巧克力减1            }            if(a[i]==0) y[++ny]=i;   //如果有空盒子 那么++ny        }        for(int i=1;i<=nx;i++)            for(int j=1;j<=ny;j++)                love[i][j]=-min(abs(x[i]-y[j]),n-abs(x[i]-y[j]));                //注意这里要取负数 求出最小的移动步数        cout<<-KM()<
     
    
   

学如逆水行舟，不进则退

转载地址：https://chocolate.blog.csdn.net/article/details/97612452 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！