首页 > 代码库 > poj3270

poj3270

2024-11-24 15:40:02   202人阅读

这题考察的是契科夫格里斯特环。。。。。。。

。。。。。好吧我承认我在吹牛逼。。。

利用置换环的思想，我们可以找出一些置换环，对每个置换环我们可以轻易的知道这样几个规律。

令置换环长度为n，首先置换次数至少是n-1，并且每个元素至少被置换一次。如果本环内置换的话，置换的代价至少是这样的sum-mina+(n-1)*mina。我们发现这种代价是可以实现的只要每次都用最小的元素去归位另一些元素，但是这是本环内部的置换，而当本环内部的最小元素去置换整个数组中的最小元素时,可能会有更小的情况，以下是证明，如果与其他置换环中的元素交换的话与且只与其他环中的最小元素交换能是最优的

从sum-mina+(n-1)*mina角度来讲只有mina变得更小才能抵消掉交换所带来的增加值，交换后形成一个更大的环如果用本环被换的代价是等于刚刚的交换后再换回来的代价的。

技术分享
#include<iostream>#include<string.h>#include<stdio.h>#include<algorithm>using namespace std;const int maxa = 100005;int a[maxa], b[maxa], c[maxa];int judge[maxa];int main(){    int n;    while(scanf("%d", &n)!=EOF){        for(int i = 0;i  < n; i++){            scanf("%d", &a[i]);            b[i] = a[i];        }        sort(b, b+n);        for(int i = 0;i  < n; i++){            c[b[i]] = i;        }        memset(judge, 0, sizeof(judge));        int ans = 0;        for(int i = 0; i < n; i++){            int j = i;            int sum = 0;            int k = 0;            if(judge[i])continue;//printf("*");            int mina = a[j];            while(judge[j] != 1){k ++;                judge[j] = 1;                sum += a[j];                j = c[a[j]];                mina = min(mina, a[j]);            }sum -= mina;            //cout<<mina<<"<<"<<sum<<endl;            ans += min((k-1)*mina+sum, (k-1)*b[0]+sum+2*(b[0]+mina));        }        printf("%d\n", ans);    }}
View Code

 

poj3270


联系
我们