洛谷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