博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
poj 3270(置换 循环)
阅读量:7060 次
发布时间:2019-06-28

本文共 1553 字,大约阅读时间需要 5 分钟。

经典的题目,主要还是考思维,之前在想的时候只想到了在一个循环中,每次都用最小的来交换,结果忽略了一种情况,还可以选所有数中最小的来交换一个循环。

Cow Sorting
Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 6511   Accepted: 2532

Description

Farmer John's N (1 ≤ N ≤ 10,000) cows are lined up to be milked in the evening. Each cow has a unique "grumpiness" level in the range 1...100,000. Since grumpy cows are more likely to damage FJ's milking equipment, FJ would like to reorder the cows in line so they are lined up in increasing order of grumpiness. During this process, the places of any two cows (not necessarily adjacent) can be interchanged. Since grumpy cows are harder to move, it takes FJ a total of X+Y units of time to exchange two cows whose grumpiness levels are X and Y.

Please help FJ calculate the minimal time required to reorder the cows.

Input

Line 1: A single integer: 
N
Lines 2..
N+1: Each line contains a single integer: line 
i+1 describes the grumpiness of cow 
i

Output

Line 1: A single line with the minimal time required to reorder the cows in increasing order of grumpiness.

Sample Input

3231

Sample Output

7

Hint

2 3 1 : Initial order. 
2 1 3 : After interchanging cows with grumpiness 3 and 1 (time=1+3=4). 
1 2 3 : After interchanging cows with grumpiness 1 and 2 (time=2+1=3).
 
#include 
#include
#include
#include
#include
using namespace std;#define N 100100struct node{ int id; int num;}g[N];int mylink[N];int f[N],tf[N];int flag[N];long long ans;int mi;int cmp(node t,node t1){ return t.num

 

转载地址:http://lsyll.baihongyu.com/

你可能感兴趣的文章
迭代算法求平方根
查看>>
generatorConfig.xml for mariadb
查看>>
netstat命令
查看>>
超全超实用的Javascript类库和jQuery插件大全之一:Web印刷排版
查看>>
Android自定义控件CustomView2 扩展控件、组合控件
查看>>
独立 View Composer 的硬件要求
查看>>
修改登陆Jenkins后session过期的时间
查看>>
导入的maven项目添加maven依赖
查看>>
bash实现“多进程”(转)
查看>>
用nginx搭建http透明代理
查看>>
linux一切皆文件
查看>>
三层交换配路由不同(VLAN)6台PC之间通信(华为)
查看>>
2018.4.25 六周第一次课 (正则grep-过滤指定关键词)
查看>>
自动化运维系列之Ansible的简介与安装
查看>>
Python编写判断成绩的程序
查看>>
Python 扫描存活主机
查看>>
Bootstrap tab 页切换导致 webuploader 渲染失败。
查看>>
一起来学大数据|为何学习大数据,要先学Java?之茅塞顿开
查看>>
javascript document.write()方法
查看>>
路由器的远程连接和密码解密
查看>>