d118: 一串數字(這題跳過不看)
https://zerojudge.tw/ShowProblem?problemid=d118
內容 :
噢噢,有個很可愛的女生叫做小樺,她正在排骨牌,每片骨牌上都恰有一個數字。她想要選出其中的幾張骨牌,在不更動順序的情況下,找到這些骨牌所能組合的最大數。
輸入說明:
每次輸入有多組測資,每組測資佔一行。 在每組測資中,會先有一串數字,依序代表每片骨牌上的數字,最後有一個正整數n(在int範圍以內),代表她要選出其中的幾張骨牌組合成她想要的數。
輸出說明:
請輸出小樺所組合出的那個最大的數。
範例輸入:
987645821 6 ← 987645821代表9張骨牌的編號 6代表要從9張中挑6張牌
123456789 8
95655645 1
範例輸出:
987821
23456789
9
想想看,要怎麼樣才能拿到最大的數字
如果要拿最小的數字,怎麼做
策略 盡量挑前面較大的數字
#include <stdio.h>
#include <string.h>
#include <algorithm>
int pos[10][5000000] , top[10] , ptr[10] , len , N , MAX;
char G[50000001];
int main(){
while ( scanf("%s",G) == 1 ){
scanf("%d",&N);
len = strlen( G );
// 把 top 的每個值都填上0
memset( top , 0 , sizeof( top ) );
// 把 ptr 的每個值都填上
memset( ptr , 0 , sizeof( ptr ) );
for ( int i = 0 ; i < len ; i++ )
pos[G[i]-'0'][top[G[i]-'0']++] = i;
MAX = -1;
for ( int i = 1 ; i <= N ; i++ ){
bool find = false;
for ( int k = 9 ; k >= 0 && !find; k-- ){
while ( ptr[k] < top[k] && pos[k][ptr[k]] <= MAX ) ptr[k]++;
for ( ptr[k] ; ptr[k] < top[k] ; ptr[k]++ ){
if ( pos[k][ptr[k]] + N - i < len ){
MAX = pos[k][ptr[k]];
ptr[k]++;
putchar(k+'0');
find = true;
break;
}
else break;
}
}
}
puts("");
}
return 0;
}