Cow Sorting
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1600 Accepted Submission(s): 507
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).
Source
2009 Multi-University Training Contest 3 - Host by WHU
題意：給你N個排列不規則的數，任務是把它從小到大排好，每次只能交換相鄰兩個數，交換一次的代價為兩數之和，求最小代價
思路：對於當前數X，我們如果知道前面比它大的數有多少，假設為K，那麼有部分代價是確定的，那就是K*X；然後還得加上比它大的那些數之和，這就是當數列到X為止，排好所需要的最小代價。
注意本題不能用long long 必須用__int64 坑！
[cpp] #include<stdio.h>
#include<string.h>
#define ll __int64
ll c[100000+5],v[100000+5];
int n;
int Lowbit(int k)
{
return (k&-k);
}
void update(int pos,int num,int val)
{
while(pos<=n)
{
c[pos]+=num;
v[pos]+=val;
pos+=Lowbit(pos);
}
}
ll sum_count(int pos)
{
ll s=0;
while(pos>0)
{
s+=c[pos];
pos-=Lowbit(pos);
}
return s;
}
ll sum(int pos)
{
ll s=0;
while(pos>0)
{
s+=v[pos];
pos-=Lowbit(pos);
}
return s;
}
int main()
{
int i,x;
while(scanf("%d",&n)!=-1)
{
memset(c,0,sizeof(c));
memset(v,0,sizeof(v));
ll ans=0,k2,k1;
for(i=1;i<=n;i++)
{
scanf("%d",&x);
update(x,1,x);
k1=i-sum_count(x);///到此為止 比x大的個數；
///sum_count[x] 為輸入i個數的時候 x之前有sum_count[x]個比x小的數 用i相減則為大於x的個數
if(k1!=0)
{
k2=sum(n)-sum(x);///到此為止 比x大的數的和；
ans+=x*k1+k2;///到此為止 比x大的數與x交換之後的和；
}
}
printf("%I64d\n",ans);
}
return 0;
}
#include<stdio.h>
#include<string.h>
#define ll __int64
ll c[100000+5],v[100000+5];
int n;
int Lowbit(int k)
{
return (k&-k);
}
void update(int pos,int num,int val)
{
while(pos<=n)
{
c[pos]+=num;
v[pos]+=val;
pos+=Lowbit(pos);
}
}
ll sum_count(int pos)
{
ll s=0;
while(pos>0)
{
s+=c[pos];
pos-=Lowbit(pos);
}
return s;
}
ll sum(int pos)
{
ll s=0;
while(pos>0)
{
s+=v[pos];
pos-=Lowbit(pos);
}
return s;
}
int main()
{
int i,x;
while(scanf("%d",&n)!=-1)
{
memset(c,0,sizeof(c));
memset(v,0,sizeof(v));
ll ans=0,k2,k1;
for(i=1;i<=n;i++)
{
scanf("%d",&x);
update(x,1,x);
k1=i-sum_count(x);///到此為止 比x大的個數；
///sum_count[x] 為輸入i個數的時候 x之前有sum_count[x]個比x小的數 用i相減則為大於x的個數
if(k1!=0)
{
k2=sum(n)-sum(x);///到此為止 比x大的數的和；
ans+=x*k1+k2;///到此為止 比x大的數與x交換之後的和；
}
}
printf("%I64d\n",ans);
}
return 0;
}
