hdu 2838 Cow Sorting(树状数组)

hdu 2838 Cow Sorting(树状数组)

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

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
   
   
3 2 3 1

 


Sample Output
   
   
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+前面比它大的数字和。

<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;
}


版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

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

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • cv2.read 与cv2.imread的区别_vc泡腾片不能和什么一起吃

    cv2.read 与cv2.imread的区别_vc泡腾片不能和什么一起吃1、cv2.imread()接口读图像,读进来直接是BGR格式数据格式在0~255需要特别注意的是图片读出来的格式是BGR,不是我们最常见的RGB格式,颜色肯定有区别。2、cv2.cvtColor(p1,p2)是颜色空间转换函数,p1是需要转换的图片,p2是转换成何种格式。cv2.COLOR_BGR2RGB将BGR格式转换成RGB格式cv2.COLOR_BGR2GRAY将…

    2022年10月15日
  • 计算机网口在什么位置,电脑网线插路由器哪个口?

    计算机网口在什么位置,电脑网线插路由器哪个口?问:电脑网线插路由器哪个口?我的路由器上有5个接口,请问电脑用网线应该插在路由器的哪一个接口?答:普通的家用路由器上的接口有2种类型:WAN接口,LAN接口。其中WAN接口只有1个,LAN接口一般是4个(有的路由器可能只有2个、3个LAN接口)。温馨提示:WAN接口,在有的路由器中叫做:Internet接口,广域网接口等,这一点大家稍微注意一下。但绝大部分的路由器上面,标注的都是WAN接口。在安装…

  • Android Studio 3.1新特性介绍

    Android Studio 3.1新特性介绍

  • 虚拟机的光盘映像文件需要下载吗_防止vmware虚拟机被检测到

    虚拟机的光盘映像文件需要下载吗_防止vmware虚拟机被检测到在百度经验中找到了解决办法,链接如下https://jingyan.baidu.com/article/25648fc18248a99191fd00fb.html

  • 光猫桥接服务器无响应,解决光猫改为桥接后无法再次访问的问题「建议收藏」

    光猫桥接服务器无响应,解决光猫改为桥接后无法再次访问的问题「建议收藏」换了一个千兆光猫,型号是PT632。最近在研究IPv6,不停的折腾光猫的WAN口连接模式(Route和Bridge)。大概的设备结构:光猫(PT632)→路由器(网件R8000)→下端设备发现一个问题:光猫使用Route模式(路由器模式)时,光猫进行拨号,下端设备会从光猫DHCP拿地址(192.168.1.*),此时可以从下端任意设备访问到光猫管理页面光猫使用Bridge模式(桥接模式)时,路由器…

  • 实时数据库 内存数据库_实时数据库产品

    实时数据库 内存数据库_实时数据库产品这是一款实时和嵌入式软件,用来管理持续增长的复杂数据,来支持高级应用的特性。性能和可靠性,更短的产品开发周期等需求,驱使开发者在他们的设计中,考虑采用经验证的、成熟的商业数据库系统组件来,来满足应用层的这些需求。  McObject公司的eXtremeDB嵌入式数据库系列产品是将高性能、稳定性和简单易用性等特性同时融入了工业基的数据库引擎。  了解eXtremeDB产品系列或eXtreme…

    2022年10月14日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号