CF 435B Pasha Maximizes(贪心)

题目链接: [传送门][1]

Pasha Maximizes

time limit per test:1 second     memory limit per test:256 megabytes

Description

Pasha has a positive integer a without leading zeroes. Today he decided that the number is too small and he should make it larger. Unfortunately, the only operation Pasha can do is to swap two adjacent decimal digits of the integer.
Help Pasha count the maximum number he can get if he has the time to make at most k swaps.

Input

The single line contains two integers a and k (1 ≤ a ≤ 1018; 0 ≤ k ≤ 100).

Output

Print the maximum number that Pasha can get if he makes at most k swaps.

Sample Input

1990 1

300 0

1034 2

Sample Output

9190

300

3104

9907000008001234

解题思路:

题目大意:给你一个整数,为交换相邻的两个数字k次能达到的最大数字的值
简单贪心,暴力从头开始枚举,选取从枚举位置开始前k个字符中最大的,使之前移。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int main()
{
    char str[100];
    int ans[100],K,maxx,pos;
    memset(str,0,sizeof(str));
    memset(ans,0,sizeof(ans));
    while(~scanf("%s %d",str,&K))
    {
        int len = strlen(str);
        for (int i = 0; i < len; i++)
        {
            ans[i] = str[i] - '0';
        }
        bool flag = false;
        for (int i = 0; i < len; i++)
        {
            if (!K)
                break;
            maxx = 0;
            for (int j = i; j <= i + K && j < len; j++)
            {
                if (maxx < ans[j])
                {
                    maxx = ans[j];
                    pos = j;
                    flag = true;
                }
            }
            for (int j = pos; j > i; j--)
            {
                int tmp = ans[j];
                ans[j] = ans[j-1];
                ans[j-1] = tmp;
            }
            if (flag)
            {
                K = K - (pos - i);
                flag = false;
            }
        }
        for (int i = 0; i < len; i++)
        {
            printf("%d",ans[i]);
        }
        printf("\n");
        memset(str,0,sizeof(str));
        memset(ans,0,sizeof(ans));
    }
    return 0;
}
上一篇:安装redis 执行make命令时报错解决方法


下一篇:HDU 5492(DP) Find a path