Cow Sorting POJ 3270 & HDU 2838

题目大意是：一串无序的数字，要排成增序的数列，可以交换不相邻的数，每交换两个数，sum+这两个数，使得sum最小，求最小的sum。

0 ms

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<algorithm>
 4 #include<string.h>
 5 using namespace std;
 6 class A
 7 {
 8 public:
 9     int v;   //数字
10     int n;   //初始位置
11     bool visit;
12 }p[100000];
13 bool cmp(const A &a,const A &b)
14 {
15     return a.v<b.v;
16 }
17 int main(){
18     int n,m,i,j,Min,Max,Mmin,x,y,t,sum,ans2,ans1,ans,num;
19     while (~scanf("%d",&n))
20     {
21         for (i=1;i<=n;i++)
22         {
23             scanf("%d",&p[i].v);
24             p[i].n=i;
25             p[i].visit=0;
26         }
27         sort(p+1,p+n+1,cmp);
28         Min = p[1].v;
29         Max = p[n].v;     //最小数的初始位置，最大数的初始位置
30         ans = 0;                    //总和
31         for (i=1;i<=n;i++)
32         {
33             Mmin = Max*10;
34             sum = 0;
35             t = i;
36             num = 0;
37             while (p[t].visit==0)     //找到一个环
38             {
39                 num ++;                 //构成环的数的数量
40                 sum += p[t].v;
41                 Mmin = min(Mmin,p[t].v);       //找到这个环里初始位置最靠前的位置
42                 p[t].visit = 1;     //标记
43                 t = p[t].n;
44             }
45             if (num > 0)
46             {
47                 ans1 = sum + (num-2)*Mmin;
48                 ans2 = sum + Mmin + (num+1)*Min;
49                 ans += min(ans1,ans2);
50             }
51         }
52         printf("%d
",ans);
53     }
54     return 0;
55 }

View Code

详解：http://www.cnblogs.com/xin-hua/archive/2013/07/29/3222651.html

另在HDU，也有一道类似的题，但是它限制了，只有相邻的两个数才能交换。

网址：http://acm.hdu.edu.cn/showproblem.php?pid=2838

树状数组做

31 ms

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 using namespace std;
 5 const int N=100100,maxn=100000;
 6 int ccnt[N];
 7 __int64 csum[N];   //在自己之前比自己小的数
 8 int lowbit(int x)
 9 {
10     return x&(-x);
11 }
12 int main()
13 {
14     int n,x;
15     while (~scanf("%d",&n))
16     {
17         memset(ccnt,0,sizeof(ccnt));
18         memset(csum,0,sizeof(csum));
19         int scnt=0;
20         __int64 ssum=0,ans=0;
21         while (n--)
22         {
23             scanf("%d",&x);
24             scnt++; ssum+=x;
25             for(int i=x;i<=maxn;i+=lowbit(i))
26                 ccnt[i]++, csum[i]+=x;       //更新csum[i]的值，ccnt[i]为csum[i]的子的个数
27             int cnt=0;
28             __int64 sum=0;
29             for(int i=x;i>0;i-=lowbit(i))
30                 cnt+=ccnt[i], sum+=csum[i];     //sum在x之前比x小的数的和,在x之前比x小的数的个数
31             ans+=ssum-sum+(__int64)x*(scnt-cnt);
32         }
33         printf("%I64d
",ans);
34     }
35     return 0;
36 }

View Code