這是我通過的方式，僅供參考而且不一定是正確的
此題要使用遞迴版的Greedy+優化輸出
除了C/C++ 我想其他的語言應該有點難通過
什麼時遞迴版的Greedy呢?
來舉例一下好了 987645821 6
need=6
首先先找9
後面還有還有8個，所以可以輸出第1個9 need=5
之後找不到 9，跳到下一個數字 8
首先找到第1個 8，後面還有7個可以輸出第1個8 need=4
再來找到第2個 8，但是後面只有 2個，而我卻要除了這個8以外 還要3個 (兩個都是取後面的)
所以我必須從上一個8跟這個8之間取 3-2 個 所以取到 7
之後退回原本的 8 ，但是之後掃到尾吧，沒有發現8
往下一個數字 7 開始掃，....掃到 2 need=1 掃到1 need=0
大致上是這樣，不過這樣應該是聽不懂的
自己想想看吧
By 想破頭的我 (而且還在AC邊緣...)
提供一下程式碼好了，以及程式碼的說明
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char s[35867525];
void Greedy (int now,int start,int end,int need)
{
if(now==-1||need==0) return;
int a,last=start-1; /*start-1 是可能之間都沒有該數字...*/
for(a=start;a<=end;a++) /*在之間取需要的個數*/
if(s[a]-48==now)
{
if((end-a)<need) /* 若無法在剩餘的數字中取到足夠的個數 則在上一次出現的位子中取數 */
{
Greedy (now-1,last+1,a-1,need-(end-a)-1); /*不足的往數字(now-1) 從上一次數字(now)出現的位子 到 這個數(now)之前 取不足的數字*/
putchar(now+48); /*退回來之後 輸出 now*/
need=end-a; /*需要的個數改變*/
last=a; /*紀錄上一次的位子*/
}
else
{
putchar(now+48);
last=a; /*紀錄上一次的位子*/
need--; /*需要的個數一直減少*/
}
if(need==0) return; /*若已經達到目標了 則結束*/
}
if(need!=0) Greedy (now-1,last+1,end,need);
/* 取了或者根本沒取 需求不足 則從上一次紀錄的地方往結尾去找 下一個數字(now-1)*/
}
main()
{
int n;
while(scanf("%s %d",s,&n)==2)
{
Greedy (9,0,strlen(s)-1,n);/*先找數字 9*/
printf("\n");
}
return 0;
}
說真的，我其實不是很了解我自己在打什麼(被鬼附身)，也不知道這支程式碼是快在哪裡...
不過大致上一定要優化輸出，不然毫無勝算...
如果出題者還想增加更強的測資話...恐怕又要在當機一次了
這個算是什麼演算法呢 ? 看起來不太像Greedy...也不太像是 D&C ...
#include<stdlib.h>
#include<string.h>
char s[35867525];
void Greedy (int now,int start,int end,int need)
{
if(now==-1||need==0) return;
int a,last=start-1; /*start-1 是可能之間都沒有該數字...*/
for(a=start;a<=end;a++) /*在之間取需要的個數*/
if(s[a]-48==now)
{
if((end-a)>=need)
{
putchar(now+48);
last=a; /*紀錄上一次的位子*/
need--; /*需要的個數一直減少*/
if(need==0) return;
}
else /* 若無法在剩餘的數字中取到足夠的個數 則在上一次出現的位子中取數 */
{
Greedy (now-1,last+1,a-1,need-(end-a)-1); /*不足的往數字(now-1) 從上一次數字(now)出現的位子 到 這個數(now)之前 取不足的數字*/
for(a=a;a<=end;a++)/*退回來之後 輸出剩餘的全部*/
putchar(s[a]);
return;
}
}
if(need!=0) Greedy (now-1,last+1,end,need);
/* 取了或者根本沒取 需求不足 則從上一次紀錄的地方往結尾去找 下一個數字(now-1)*/
}
main()
{
int n;
while(scanf("%s %d",s,&n)==2)
{
Greedy (9,0,strlen(s)-1,n);/*先找數字 9*/
printf("\n");
}
return 0;
}
提供一下程式碼好了，以及程式碼的說明
#include
#include
#include
char s[35867525];
void Greedy (int now,int start,int end,int need)
{
if(now==-1||need==0) return;
int a,last=start-1; /*start-1 是可能之間都沒有該數字...*/
for(a=start;a<=end;a++) /*在之間取需要的個數*/
if(s[a]-48==now)
{
if((end-a) {
Greedy (now-1,last+1,a-1,need-(end-a)-1); /*不足的往數字(now-1) 從上一次數字(now)出現的位子 到 這個數(now)之前 取不足的數字*/
putchar(now+48); /*退回來之後 輸出 now*/
need=end-a; /*需要的個數改變*/
last=a; /*紀錄上一次的位子*/
}
else
{
putchar(now+48);
last=a; /*紀錄上一次的位子*/
need--; /*需要的個數一直減少*/
}
if(need==0) return; /*若已經達到目標了 則結束*/
}
if(need!=0) Greedy (now-1,last+1,end,need);
/* 取了或者根本沒取 需求不足 則從上一次紀錄的地方往結尾去找 下一個數字(now-1)*/
}
main()
{
int n;
while(scanf("%s %d",s,&n)==2)
{
Greedy (9,0,strlen(s)-1,n);/*先找數字 9*/
printf("\n");
}
return 0;
}
說真的，我其實不是很了解我自己在打什麼(被鬼附身)，也不知道這支程式碼是快在哪裡...
不過大致上一定要優化輸出，不然毫無勝算...
如果出題者還想增加更強的測資話...恐怕又要在當機一次了
這個算是什麼演算法呢 ? 看起來不太像Greedy...也不太像是 D&C ...
剛剛有人教我就做出來了
(畢竟提示我的人事個大神)
適用stack實做的....遇到大的就把小的丟出來大的插入
2xx豪秒就可以過了
這題的正解再下面.....雖然寫的不是很好.....也沒有註解
不過短短的很可愛
就看看吧
#include <stdio.h>
#include <string.h>
char str[50000000];
char ans[50000000];
int top;
int main()
{
int n;
int len;
while(scanf("%s", str) != EOF)
{
scanf("%d", &n);
len = strlen(str);
top = 1;
ans[0] = str[0];
for(int i=1 ; i<len ; i++)
{
if(top+len-i <= n)
{
for(int j=i ; j<len ; j++)
{
ans[top] = str[j];
top++;
}
break;
}
while(str[i] > ans[top-1])
{
top--;
if(top == 0)
break;
if(top+len-i <= n)
break;
}
ans[top] = str[i];
top++;
}
if(top > n)
top = n;
for(int j=0 ; j<top ; j++)
putchar(ans[j]);
puts("");
}
return 0;
}
這是我通過的方式，僅供參考而且不一定是正確的
此題要使用遞迴版的Greedy+優化輸出
除了C/C++ 我想其他的語言應該有點難通過
什麼時遞迴版的Greedy呢?
來舉例一下好了 987645821 6
need=6
首先先找9
後面還有還有8個，所以可以輸出第1個9 need=5
之後找不到 9，跳到下一個數字 8
首先找到第1個 8，後面還有7個可以輸出第1個8 need=4
再來找到第2個 8，但是後面只有 2個，而我卻要除了這個8以外 還要3個 (兩個都是取後面的)
所以我必須從上一個8跟這個8之間取 3-2 個 所以取到 7
之後退回原本的 8 ，但是之後掃到尾吧，沒有發現8
往下一個數字 7 開始掃，....掃到 2 need=1 掃到1 need=0
大致上是這樣，不過這樣應該是聽不懂的
自己想想看吧
By 想破頭的我 (而且還在AC邊緣...)
我想出了一個 O(L) 的方法 ( L 為字串長度 ) 只是時間複雜度還是不理想
#include <stdio.h>
#include <string.h>
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 );
memset( top , 0 , sizeof( top ) );
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] < 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;
}