洛谷P1053 篝火晚會
貪心 數學 桶
假如兩個串其中一個串要變成另一個 串，需要的代價 為對應位置上不同的數的個數
因為如果對應位置上的數不同，那他一定在一個交換環上，交換環上如果有 m個數交換，需要代價就是 m
但是 不一定就是這個串代價最小，因為可以目前串不變，另一個串循環位移，變成他的循環同構串，
然後問題就變成了求一個串的任意循環同構串，使其與 串 1.2.3.4.5 的對應位置上的不同的數最少
但如果每一次都這樣循環位移，n^2 顯然會炸
考慮優化，我們開一個桶，dp[ i ]表示有幾個數經過位移 i 位 之後能與 原數相同，這樣取最大的dp[ i ]
然後答案就是 n - max( dp[ i ] )
但要注意因為是圓排列，是以方向反一下沒關系，然後就方向反一下 在做一遍就行了
1、注意桶 清0 也要清空 我忘記清空了 QAQ
2、還有注意一下一個數的情況
3、還有用過的數不能在用 萬一所有的數左都為 1 右邊也都為 1 就出事了
1 #include <cstdio>
2 #include <cstring>
3 #include <cmath>
4 #include <cstdlib>
5 #include <string>
6 #include <algorithm>
7 #include <iomanip>
8 #include <iostream>
9 using namespace std ;
10
11 const int maxn = 50011 ;
12 struct node{
13 int l,r ;
14 };
15 node a[maxn] ;
16 int n,w,ans,mi ;
17 int old[maxn],neww[maxn],dp[maxn],used[maxn] ;
18
19 inline void fail()
20 {
21 printf("-1\n") ;
22 exit(0) ;
23 }
24
25 inline int calc()
26 {
27 int x,ans = 0 ;
28 for(int i=0;i<=n;i++) dp[ i ] = 0 ;
29 for(int i=1;i<=n;i++) x = ( old[ i ] - i + n ) % n,dp[x]++ ;
30 for(int i=0;i<n;i++) if( dp[ i ] > ans ) ans = dp[ i ] ;
31 return n-ans ;
32 }
33
34 int main()
35 {
36 scanf("%d",&n ) ;
37 for(int i=1;i<=n;i++)
38 scanf("%d%d",&a[ i ].l,&a[ i ].r) ;
39 old[ 1 ] = 1 ; used[ 1 ] =1 ;
40 for(int i=2;i<=n;i++)
41 {
42 if(i!=2 && a[ old[i-1] ].r==old[ i-2 ] ) swap(a[ old[i-1] ].r,a[ old[i-1] ].l);
43 if( used[ a[ old[i-1] ].r ] ) fail() ;
44 used[ a[ old[i-1] ].r ] = 1 ;
45 old[ i ] = a[ old[i-1] ].r ;
46 }
47 if(n!=1 && a[ old[n] ].r==old[ n-1 ] ) swap(a[ old[n] ].r,a[ old[n] ].l) ;
48
49
50 if(a[ old[n] ].r!=old[ 1 ]) fail() ;
51 if(a[ old[1] ].l!=old[ n ]) fail() ;
52 for(int i=2;i<=n;i++)
53 if(a[old[ i ]].l!=old[i-1]) fail() ;
54 for(int i=1;i<=n;i++) neww[ i ] = i ;
55
56 mi = 1e9 ;
57 mi = calc() ;
58 for(int i=1,zz = n/2;i<=zz;i++)
59 swap(old[ i ],old[n-i+1]) ;
60 w = calc() ;
61 if( mi > w ) mi = w ;
62 printf("%d\n",mi) ;
63 return 0 ;
64 } 轉載于:https://www.cnblogs.com/third2333/p/6970337.html