題目請參考 https://zerojudge.tw/ShowProblem?problemid=f648.
這題受記憶體限制15MB, 卻又有高達100萬筆的測資在第一行, 針對這種沒有什麼夠小的資料結構可以放下的題目, 請參考另一篇(e080. read and write)的方法來自由讀取stdin.
我先尋找換行符號以便先跳過第一行的大筆資料, 順便存起換行符號的位置在ENDL_index.
//用1MB當stdio的buffer
#define buffer_size 1048577 //1024*1024+1
char buffer[buffer_size];
int ENDL_index=0; //換行符號的位置
//尋找換行符號位置
void FindENDL(){
while(1){
int n=fread(buffer,1, buffer_size, stdin);
ENDL_index+=n;
for(int i=0;i<n;i++){
if(buffer[i]=='\n'){
ENDL_index=ENDL_index-n+i;
return;
}
}
}
}然後讀第二行, 用陣列和set儲存要檢查的名單. 為什麼要放兩份? 因為檢查的名單也有可能有重複的名字, 測資似乎真的是這樣. 放在set裡的就會只有一份, 有排序過搜尋也比較快.
class check{
public:
//朋友的名字
string name;
//重複的次數
int count;
check(){
count=0;
}
};
//儲存要查的名字
check check_name[1000];
int check_name_count=0;
//把要查的名字放入陣列, 測資可能有重複
void AddCheckName(char *name){
check_name[check_name_count++].name=string(name);
}
//把要查的名字放入check_set, 避免重複, 加快搜尋
class Compare{
public:
bool operator()(check const &a, check const &b) const {
return a.name<b.name;
}
};
set<check, Compare> check_set;
//儲存要檢查的名字
void ReadCheckName(){
char checkName[11];
fseek(stdin, ENDL_index, SEEK_SET);
while(fscanf(stdin,"%s", checkName)!=EOF){
AddCheckName(checkName); //放入陣列一份
check_set.insert(check_name[check_name_count-1]); //放入set一份
}
}然後就可以倒帶回去再讀一次第一行的測資. 每讀一個名字就檢查在不在check_set裡, 如果在就把count++. 全部處理完第一行後,就可以根據每個名字的count來輸出結果.
//倒帶回stdin開頭
rewind(stdin);
int pos=0;
char name[11];
while(pos<=ENDL_index){
check c;
scanf("%s", name);
c.name=name;
//尋找有沒有要檢查的名字
auto it=check_set.find(c);
if(it != check_set.end()){
//找到一次就加一次
((check&)*it).count++;
}
pos+=strlen(name)+1;
}
//輸出結果
for(int i=0;i<check_name_count;i++){
auto it=check_set.find(check_name[i]);
int n=((check&)*it).count;
if(n==0){
printf("No\n");
}else if(n==1){
printf("Yes\n");
}else{
printf("Pathetic\n");
}
}這樣AC差不多0.4秒. 當然你也可以反過來做, 用第二行的資料去找在不在第一行的名字裡, 只要把第一行資料分小段, 多找幾次就可以了. 如果以一千個名字當一段, 我試過AC差不多要一秒.
完整程式如下.
#include <iostream>
#include <stdio.h>
#include <set>
#include <string.h>
using namespace std;
class check{
public:
//朋友的名字
string name;
//重複的次數
int count;
check(){
count=0;
}
};
//儲存要查的名字
check check_name[1000];
int check_name_count=0;
//把要查的名字放入陣列, 測資可能有重複
void AddCheckName(char *name){
check_name[check_name_count++].name=string(name);
}
//把要查的名字放入check_set, 避免重複, 加快搜尋
class Compare{
public:
bool operator()(check const &a, check const &b) const {
return a.name<b.name;
}
};
set<check, Compare> check_set;
//用1MB當stdio的buffer
#define buffer_size 1048577 //1024*1024+1
char buffer[buffer_size];
int ENDL_index=0; //換行符號的位置
//尋找換行符號位置
void FindENDL(){
while(1){
int n=fread(buffer,1, buffer_size, stdin);
ENDL_index+=n;
for(int i=0;i<n;i++){
if(buffer[i]=='\n'){
ENDL_index=ENDL_index-n+i;
return;
}
}
}
}
//儲存要檢查的名字
void ReadCheckName(){
char checkName[11];
fseek(stdin, ENDL_index, SEEK_SET);
while(fscanf(stdin,"%s", checkName)!=EOF){
AddCheckName(checkName); //放入陣列一份
check_set.insert(check_name[check_name_count-1]); //放入set一份
}
}
int main(){
//尋找換行符號位置
FindENDL();
//儲存要檢查的名字
ReadCheckName();
//倒帶回stdin開頭
rewind(stdin);
int pos=0;
char name[11];
while(pos<=ENDL_index){
check c;
scanf("%s", name);
c.name=name;
//尋找有沒有要檢查的名字
auto it=check_set.find(c);
if(it != check_set.end()){
//找到一次就加一次
((check&)*it).count++;
}
pos+=strlen(name)+1;
}
//輸出結果
for(int i=0;i<check_name_count;i++){
auto it=check_set.find(check_name[i]);
int n=((check&)*it).count;
if(n==0){
printf("No\n");
}else if(n==1){
printf("Yes\n");
}else{
printf("Pathetic\n");
}
}
}