题目链接: [传送门][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;
}