文档章节

洛谷P2127 序列排序 [贪心]

o
 osc_x4h57ch8
发布于 2018/04/24 13:55
字数 628
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

  题目传送门

  


 

题目描述

 

小C有一个N个数的整数序列,这个序列的中的数两两不同。小C每次可以交换序列中的任意两个数,代价为这两个数之和。小C希望将整个序列升序排序,问小C需要的最小代价是多少?

 

输入输出格式

输入格式:

 

 

第一行,一个整数N。

 

第二行,N个整数,表示小C的序列。

 

 

输出格式:

 

 

一行,一个整数,表示小C需要的最小代价。

 

 

 

输入输出样例

 

输入样例#1: 复制
6
8 4 5 3 2 7
输出样例#1: 复制
34

 

说明

 

数据范围:

 

对于30%的数据,1<=N<=10;

 

对于全部的数据,1<=N<=100000,输入数据中的其他整数均为正整数且不超过109。

 

 


  

  分析:很显然的贪心。因为每次只能交换两个数,那么每次都拿小的数来交换肯定会更优。但肯定不会这么简单。首先从样例分析,样例中的8,2,7这三个数只要互相交换就可以到达目标位置,也就是说这三个数形成了一个“环”,那么每次就照这样的环,将环中的每一个数归位的最小花费只有两种情况:要么就每次都拿环中最小的数与每一个数相互交换,要么就拿整个序列中最小的数与环中每个数交换。不过要注意,第二种情况交换的时候有一个数会交换两次(可以自己模拟一下),那么肯定就将环中最小的数交换两次最优。具体看代码:

  Code:

 

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
using namespace std;
const int N=1e5+7;
int n;
bool vis[N];
long long ans;
struct Node{
  int val,pos;
}a[N];
inline int read()
{
  char ch=getchar();int num=0;bool flag=false;
  while(ch<'0'||ch>'9'){if(ch=='-')flag=true;ch=getchar();}
  while(ch>='0'&&ch<='9'){num=num*10+ch-'0';ch=getchar();}
  return flag?-num:num;
}
bool cmp(Node x,Node y)
{return x.val<y.val;}
inline void work(int x)
{
  long long tot=0,num=0,minn=1e9+7;
  while(!vis[x]){
    vis[x]=true;tot++;
    num+=a[x].val;
    if(a[x].val<minn)
      minn=a[x].val;
    x=a[x].pos;}
  long long a1=num+(tot-2)*minn;
  long long a2=num+(tot+1)*a[1].val+minn;
  ans+=min(a1,a2);
}
int main()
{
  n=read();
  for(int i=1;i<=n;i++){
    a[i].val=read();
    a[i].pos=i;}
  sort(a+1,a+n+1,cmp);
  for(int i=1;i<=n;i++)
    if(!vis[i])
      work(i);
  printf("%lld",ans);
  return 0;
}

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

Git本地分支和远程分支关联

转载:https://blog.csdn.net/cherishhere/article/details/52606884 转载:https://blog.zengrong.net/post/1746.html 转载:https://blog.csdn.net/xinghuowuzhao/article/details/78663526 转......

osc_ur9jjorb
14分钟前
10
0
移动应用测试方法与思路

标签(空格分隔): 浅谈移动应用测试方法与思路 在 GUI 自动化测试这个系列,我讲了很多基于浏览器的业务测试的内容,你可能会说,现在移动 App 大行其道,对移动应用测试的方法和思路才更重...

osc_avdbd8s3
16分钟前
9
0
搜索所有Git历史记录中的字符串? [重复] - Search all of Git history for a string? [duplicate]

问题: This question already has an answer here: 这个问题在这里已有答案: How to grep Git commit diffs or contents for a certain word? 如何grep Git为某个单词提交差异或内容? 8 ...

fyin1314
17分钟前
12
0
css实现圆形倒计时效果

实现思想: 1.最外层包裹内部的div1(.box) 2.内部左右两边div2(.left_box和.right_box),宽度为div1的一半,通过overflow:hidden隐藏其内部的div 3.在左右两个div2中各有一个div3(.left_item...

osc_sg74u54s
17分钟前
7
0
python语言中threading.Thread类的使用方法

1. 编程语言里面的任务和线程是很重要的一个功能。在python里面,线程的创建有两种方式,其一使用Thread类创建 # 导入Python标准库中的Thread模块 from threading import Thread # 创建一...

osc_q5urtsdm
18分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部