大家好，又见面了，我是全栈君。
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.
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
7HintInput 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账号...
