POJ3270 cow sorting 【polya】

2024-06-17 03:32
文章标签 cow sorting polya poj3270

本文主要是介绍POJ3270 cow sorting 【polya】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述:

给你一个数字序列(每个数字唯一),每次你可以交换任意两个数字,代价为这两个数字的和,问最少用多少代价能把这个序列按升序排列好。

题目的具体做法是参考刘汝佳的《算法艺术与信息学奥赛》大概思路是:以后再用别种方法解,
1.找出初始状态和目标状态。明显,目标状态就是排序后的状态。
2.画出置换群,在里面找循环。例如,数字是8 4 5 3 2 7
明显,                                   目标状态是2 3 4 5 7 8,能写为两个循环:(8 2 7)(4 3 5)。
3.观察其中一个循环,明显地,要使交换代价最小,应该用循环里面最小的数字2,去与另外的两个数字,7与8交换。这样交换的代价是:
sum - min + (len - 1) * min
化简后为:
sum + (len - 2) * min
其中,sum为这个循环所有数字的和,len为长度,min为这个环里面最小的数字。

4.考虑到另外一种情况,我们可以从别的循环里面调一个数字,进入这个循环之中,使交换代价更小。例如初始状态:1 8 9 76
可分解为两个循环:(1)(8 6 9 7),明显,第二个循环为(8 6 97),最小的数字为6。我们可以抽调整个数列最小的数字1进入这个循环。使第二个循环变为:(8 1 97)。让这个1完成任务后,再和6交换,让6重新回到循环之后。这样做的代价明显是:
sum + min + (len + 1) * smallest
其中,sum为这个循环所有数字的和,len为长度,min为这个环里面最小的数字,smallest是整个数列最小的数字。

5.因此,对一个循环的排序,其代价是sum - min + (len - 1) * min和sum + min + (len +1) * smallest之中小的那个数字。但这里两个公式还不知道怎么推出来的。
6.我们在计算循环的时候,不需要记录这个循环的所有元素,只需要记录这个循环的最小的数及其和。

7.在储存数目的时候,我们可以使用一个hash结构,将元素及其位置对应起来,以达到知道元素,可以快速反查元素位置的目的。这样就不必要一个个去搜索。


#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int seq[11111];
int to[11111];
int indexn[1111100];
bool vis[1111100];
int main()
{int n;while(scanf("%d",&n)!=EOF){memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++){scanf("%d",&seq[i]);indexn[seq[i]]=i;to[i]=seq[i];}sort(to+1,to+1+n);int res=0;for(int i=1;i<=n;i++){if(!vis[i]){int start=seq[i];int minn=9999999;int len=0;int sum=0;int now=i;do{vis[now]=true;sum+=seq[now];len++;minn=min(minn,seq[now]);if(to[now]==start)break;now=indexn[to[now]];}while(true);int sum1=sum-minn+(len-1)*minn;int sum2=sum+minn+(len+1)*to[1];res+=min(sum1,sum2);}}cout<<res<<endl;}return 0;
}


这篇关于POJ3270 cow sorting 【polya】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1068365

相关文章

Sorting It All Out POJ(拓扑排序+floyd)

一个就是简单的拓扑排序,一个就是利用floyd判断是否存在环 #include<cstdio>#include<cstring>#include<vector>#include<queue>using namespace std;#define MAXD 30#define MAX_SIZE 1000vector<int>G[MAXD];int n,m;char L[MAX

[LeetCode] 969. Pancake Sorting

题:https://leetcode.com/problems/pancake-sorting 题目大意 对于数组A,可进行 k-reverse操作,即将 前k个元素翻转,求能使A为升序的 k-reverse 操作顺序。 解题思路 分析k操作,k-reverse操作只会影响 前面的数,不会影响 数组中后面的数,所以思路是逐步将最大元素 放置在合适的位置。 先拷贝 A 为 Abackup,

【POJ】3660 Cow Contest floyd(可以拓扑排序?)

Cow Contest Time Limit: 1000MS Memory Limit: 65536KTotal Submissions: 6925 Accepted: 3792 Description N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are participating i

BFS —— POJ 3278 Catch That Cow

对应POJ题目:点击打开链接 Catch That Cow Time Limit: 2000MS Memory Limit: 65536KTotal Submissions: 54686 Accepted: 17096 Description Farmer John has been informed of the location of a fugitive cow

USACO Section 2.3 Cow Pedigrees

题意: N个节点  深度为K  的正则二叉树  求  树有几种形态 思路: 一开始以为是数学题…  看了byvoid的题解才知道是dp… 每棵树由根节点、左子树、右子树构成  由此得状态转移  树=左子树*右子树 节点数和深度是影响答案的属性  所以令dp[i][j]表示i个节点深度在j以内的树的形态数 深度在j以内的树又两个深度在j-1以内的树和一个根节点构成 设左子树k个节

Codeforces 283. B. Cow Program记忆化搜索

output standard output Farmer John has just given the cows a program to play with! The program contains two integer variables, x and y, and performs the following operations on a sequence a1, a2, ..

Sorting (Merge Sort, Rainball Sort, quick select) 总结

Merge k Sorted Lists (这题是用PQ,或者merge sort都可以做,关于第K大的问题,参考: Find Kth 题目类型总结) Sort an Array (重点掌握merge sort和quick sort,因为两者可以演变为,divide conquer, quick select, 参考: Find Kth 题目类型总结) Sort Colors 思路:三指针,i

【POJ3270】【Cow Sorting】

Cow Sorting Time Limit: 2000MS Memory Limit: 65536KTotal Submissions: 6411 Accepted: 2488 Description Farmer John's N (1 ≤ N ≤ 10,000) cows are lined up to be milked in the evening. Each

【POJ3268】【Silver Cow Party】【反向dij】【sizeof失效】

Silver Cow Party Time Limit: 2000MS Memory Limit: 65536KTotal Submissions: 15522 Accepted: 7039 Description One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1..N is going

POJ 1985 Cow Marathon(树的直径)

题目链接 题意:给出一棵树,求出这个树的直径 解答:任选一点进行dfs,会找到一个最远点s,在以这个最远点s进行dfs,会找到一个最远点是t,那么s-t就是树的直径。 //#include<bits/stdc++.h>#include<cstdio>#include<algorithm>#include<vector>#include<cstring>using namespace