文档章节

HDU 6351 (Beautiful Now) 2018 Multi-University Training Contest 5

o
 osc_1ee7cxmx
发布于 2018/08/06 20:45
字数 416
阅读 0
收藏 0

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

题意:给定数N(1<=N<=1e9),k(1<=k<=1e9),求对N的任意两位数交换至多k次能得到的最小与最大的数,每一次交换之后不能出现前导零。

因为N最多只有10位,且给了2500ms,当时觉得可以枚举全排列,再判断前导零和最少交换次数。

最少交换次数是(每个循环节中的个数-1)之和。

当时想的是全排列N的每位数,但是这样会出现一个问题:N中可能出现相同的数,这样求循环节中元素个数就会很困难。‘

其实应该对下标进行全排列,因为下标是不可能相同的,这样就可以O(len) 地计算出每个排列的最少交换次数。然后取符合条件的最小最大的数为答案。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn =10;
const LL INF= (1LL)<<60;
int k,len;
int pos[maxn];
int num[maxn];
bool vis[maxn];

int check(){
    memset(vis,0,sizeof(vis));
    int cnt =0;
    for(int i=0;i<len;++i){
        if(vis[i]) continue;
        int tmp=0;
        while(!vis[i]){
            tmp++;
            vis[i]=1;
            i = pos[i];
        }
        cnt += tmp-1;
        if(cnt>k) return 0;
    }
    return cnt;
}


char str[maxn];
int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int T;
    scanf("%d",&T);
    while(T--){
        memset(str,0,sizeof(str));
        scanf("%s %d",str,&k);
        len = strlen(str);
        LL N=0;
        for(int i=0;i<len;++i) num[i] = str[i]-'0',pos[i]=i,N = N*10+num[i];
        LL ans1= N,ans2=N;
        do{
            if(num[pos[0]]!=0 && check()){
                LL tmp =0;
                for(int i=0;i<len;++i){
                    tmp*=10;
                    tmp+= num[pos[i]];
                }
                if(tmp<ans1) ans1=tmp;
                if(tmp>ans2) ans2=tmp;
            }
        }while(next_permutation(pos,pos+len));
        printf("%lld %lld\n",ans1,ans2);
    }
    return 0;
}

 

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

暂无文章

格式编号始终显示2个小数位 - Format number to always show 2 decimal places

问题: I would like to format my numbers to always display 2 decimal places, rounding where applicable. 我想将数字格式化为始终显示2个小数位,并在适用的情况下四舍五入。 Examples...

富含淀粉
41分钟前
22
0
Docker可视化工具Portainer

1 前言 从没想到Docker也有可视化的工具,因为它的命令还是非常清晰简单的。无聊搜了一下,原来已经有很多Docker可视化工具了。如DockerUI、Shipyard、Rancher、Portainer等。查看对比了一番...

南瓜慢说
43分钟前
20
0
日志系统新贵 Loki,真香!!

最近,在对公司容器云的日志方案进行设计的时候,发现主流的ELK或者EFK比较重,再加上现阶段对于ES复杂的搜索功能很多都用不上最终选择了Grafana开源的Loki日志系统,下面介绍下Loki的背景。...

庞陆阳
57分钟前
14
0
jQuery获取select onChange的值 - jQuery get value of select onChange

问题: I was under the impression that I could get the value of a select input by doing this $(this).val(); 我的印象是我可以通过执行$(this).val();来获取选择输入的值$(this).val()......

javail
今天
13
0
道翰天琼解密宇宙信息大脑三者最核心奥秘,破解认知智能基础理论(群聊形式)

三体论是探索研究宇宙,信息和人类大脑三者关系的理论体系。是认知智能的奠基理论体系之一。宇宙和信息,信息和人类大脑,人类大脑和宇宙,三者之间存在着某种未被完全揭示的奥秘。三体论的核...

jackli2020
今天
15
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部