前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >hdu 2838 Cow Sorting(树状数组)

hdu 2838 Cow Sorting(树状数组)

作者头像
全栈程序员站长
发布2022-07-07 17:53:49
1970
发布2022-07-07 17:53:49
举报

大家好,又见面了,我是全栈君。

Cow Sorting

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2239 Accepted Submission(s): 711

Problem Description

Sherlock’s N (1 ≤ N ≤ 100,000) cows are lined up to be milked in the evening. Each cow has a unique “grumpiness” level in the range 1…100,000. Since grumpy cows are more likely to damage Sherlock’s milking equipment, Sherlock would like to reorder the cows in line so they are lined up in increasing order of grumpiness. During this process, the places of any two cows (necessarily adjacent) can be interchanged. Since grumpy cows are harder to move, it takes Sherlock a total of X + Y units of time to exchange two cows whose grumpiness levels are X and Y.

Please help Sherlock calculate the minimal time required to reorder the cows.

Input

Line 1: A single integer: N Lines 2..N + 1: Each line contains a single integer: line i + 1 describes the grumpiness of cow i.

Output

Line 1: A single line with the minimal time required to reorder the cows in increasing order of grumpiness.

Sample Input

代码语言:javascript
复制
    3
2
3
1

Sample Output

代码语言:javascript
复制
    7


    
     
      
      Hint 
      Input Details Three cows are standing in line with respective grumpiness levels 2, 3, and 1. Output Details 2 3 1 : Initial order. 2 1 3 : After interchanging cows with grumpiness 3 and 1 (time=1+3=4). 1 2 3 : After interchanging cows with grumpiness 1 and 2 (time=2+1=3). 

题意:给出一组数从1到N打乱,要求把数组又一次有序(从小到大),仅仅能交换相邻的两个数字。代价为相邻两个数字和。求最小代价?

思路:对于每一个数字x,我们仅仅须要把它和前面比它大的数字交换。求出交换代价,反复运行就能得出答案。

这个代价就是,比它大的数字个数t*x+前面比它大的数字和。

代码语言:javascript
复制
<pre name="code" class="cpp">#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<vector>
#include<functional>
#include<iostream>
using namespace std;
#define N 100005
#define ll __int64
int a[N],cnt[N],n;   //记录数字个数
ll sum[N];      //记录数字和
int lowbit(int x)
{
    return x&(-x);
}
void add(int x)
{
    int d=x;
    while(x<=n)
    {
        cnt[x]++;
        sum[x]+=d;
        x+=lowbit(x);
    }
}
int sum1(int x)   //求比x小的数字已经出现几个(包含x)
{
    int s=0;
    while(x)
    {
        s+=cnt[x];
        x-=lowbit(x);
    }
    return s;
}
ll sum2(int x)  //求当前出现的比x大的数字和
{
    ll s=0;
    while(x)
    {
        s+=sum[x];
        x-=lowbit(x);
    }
    return s;
}
int main()
{
    int i,k,t;
    while(scanf("%d",&n)!=-1)
    {
        memset(cnt,0,sizeof(cnt));
        memset(sum,0,sizeof(sum));
        ll ans=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            add(a[i]);
            t=sum1(a[i]);  
            k=i-t;   //前面有几个比x大的数
            if(k!=0)
            {
                ans+=(ll)a[i]*k;       //注意数字会超出int
                ans+=sum2(n)-sum2(a[i]);  //求当前位置出现的比x大的数字和
            }
        }
        printf("%I64d\n",ans);
    }
    return 0;
}

发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/116466.html原文链接:https://javaforall.cn

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022年1月2,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Cow Sorting
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档