XidianOJ 1123 K=1 Problem of Orz Pandas

gaojinguan

题目描述


　　One panda named orz is playing a interesting game, he gets a big integer Num and an integer K. In this game, he can exchange two single numbers in Num. For example, he can get 1243 from 3241 by exchange 1 and 3.But orz can exchange at most K times. So what’s the biggest number after at most K times operations?
　　However, a VIP (Very Important Panda) of ACM/OPPC (Orz Panda Programming Contest) comittee thought this problem was too hard for Orz Pandas. So he simplified this problem with constraint K=1. Your task is to solve the simplified problem.

输入


　　Multiple cases. For each case:
The first line is an integer Num. 0 ≤ Num ≤ 101000, and it is guaranteed that Num is a legal integer and doesn’t contain any leading zero

输出


　　For each test case, print the biggest number after at most 1 times operation in a line.


--正文

字符串读取数，贪心找可能的数进行交换




#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
char num[1001];
int findMax(char* num){
int len = strlen(num);
int max = -1,maxi;
int i;
for (i=0;i<len;i++){
if (num - '0' >= max) {
max = num - '0';
maxi = i;
}
}
return maxi;
}
int main(){
while (scanf("%s",num) != EOF){
char* begin = num;
int len = strlen(num);
int total = 0;
bool over = false;
while (!over){
int maxi = findMax(&num[total]) + total;
int now = total;
while (num[now] == num[maxi] && now < maxi) now++;
if (now == maxi) {
total = maxi+1;
if (num[total] == '\0') break;
continue;
}
else {
char temp = num[now];
num[now] = num[maxi];
num[maxi] = temp;
break;
}
}
printf("%s\n",begin);
}
return 0;
}