題目請參考 https://zerojudge.tw/ShowProblem?problemid=e080.
我們通常解題, 都是依序讀取測資的, 如果像這題測資很大, 就要把測資存在某種資料結構裡. 但是這題加上了使用記憶體的限制. 看似怎麼樣都找不出足夠的記憶體來儲存測資. 如果有辦法可以先讀測資的第二個數字, 再讀測資的第一個數字, 問題就解決了.
一般測資我們都是依照輸入的先後順序讀取來自stdio的stdin(標準輸入), 讀完就消失了, 怎麼可能先讀後面呢? 其實是有可能的! 如果測資很大而且是存在檔案裡, 再利用重新導向(redirection)的方法餵給你的程式, 那你就可以把stdin當檔案一樣來任意讀取.
我開一個DOS視窗, 執行這題的解題程式給你看看, 測資存在檔案裡若用重導的方法可以正確執行, 同樣的一個程式, 測資用打字輸入就失敗了.
現在可以開始解題了, 我一開始用getchar()來一個byte一個byte的先讀走前面的數字, 最後雖然可以執行成功, 但是時間超過限制. 為了增加讀寫速度, 我改用fread()和print()就成功了. (fwrite是zerojudge被禁用的)
fread是一次讀取一個block的程式, 所以要在每個block裡面去找兩個數字間隔開的那個空白, 同時為了加快速度, 我記錄下那個空白的位置, 這樣回去讀第一個數字時, 我就不用再找這個空白一次, 因為我已經知道讀到哪裡就可以結束了. 下面程式是先找第二個數字把他印出來.
char a;
bool start=false; //已經讀到第二個數字,可以開始印出
int n; //每次讀回的byte數
int length=0; //紀錄空白的位置
while(1){
n=fread(buffer, 1, 1024*1024*2, stdin);
if(!n)
break;
if(start){
buffer[n]=0; //先放個結束符號0, 再用printf印出
printf("%s",buffer);
continue;
}
length+=n; //更新已讀的byte數
//找第二個數字前的那個空白
for(int i=0;i<n;i++){
a=buffer[i];
if(a==' '){ //找到了
start=true; //第二個數字開始
length=length-n+i; //紀錄空白的位置
buffer[n]=0; //先放個結束符號0, 再用printf印出
printf("%s",&buffer[i+1]);
}
}
};
印完第二個數字後, 回去stdin的開頭.可以用fseek, 或是rewind, 我用rewind, 順便印一個空白. 後面印第一個數字我就不解釋了.
//印完第二個數字後, 回去stdin的開頭
rewind(stdin);
//依題目要求印一個空白
printf(" ");
//再印第一個數字
int now=0; //記錄讀了多少byte
while(1){
n=fread(buffer, 1, 1024*1024*2, stdin);
if(!n)
break;
now+=n;
if(now<=length){ //如果還沒超過第一個數字長度
buffer[n]=0; //先放個結束符號0, 再用printf印出
printf("%s",buffer);
continue;
}
//已超過第一個數字
now-=n;
buffer[length-now]=0; //先放個結束符號0,printf最後一段
printf("%s",buffer);
break;
};完整程式如下, 這題我用2MB當buffer花了68ms AC. 其實不用這麼大也可以更快.你自己試試看吧.
#include <iostream>
#include <stdio.h>
using namespace std;
char buffer[1024*1024*2+1]; //一次讀1MB, 加一個byte放字串結束符號0.
int main(){
char a;
bool start=false; //已經讀到第二個數字,可以開始印出
int n; //每次讀回的byte數
int length=0; //紀錄空白的位置
while(1){
n=fread(buffer, 1, 1024*1024*2, stdin);
if(!n)
break;
if(start){
buffer[n]=0; //先放個結束符號0, 再用printf印出
printf("%s",buffer);
continue;
}
length+=n; //更新已讀的byte數
//找第二個數字前的那個空白
for(int i=0;i<n;i++){
a=buffer[i];
if(a==' '){ //找到了
start=true; //第二個數字開始
length=length-n+i; //紀錄空白的位置
buffer[n]=0; //先放個結束符號0, 再用printf印出
printf("%s",&buffer[i+1]);
}
}
};
//印完第二個數字後, 回去stdin的開頭
rewind(stdin);
//依題目要求印一個空白
printf(" ");
//再印第一個數字
int now=0; //記錄讀了多少byte
while(1){
n=fread(buffer, 1, 1024*1024*2, stdin);
if(!n)
break;
now+=n;
if(now<=length){ //如果還沒超過第一個數字長度
buffer[n]=0; //先放個結束符號0, 再用printf印出
printf("%s",buffer);
continue;
}
//已超過第一個數字
now-=n;
buffer[length-now]=0; //先放個結束符號0,printf最後一段
printf("%s",buffer);
break;
};
}