題目在 https://zerojudge.tw/ShowProblem?problemid=i164
這題是要根據老師的卡片的位置找出學生相同的卡片的最近距離. 寫出對的程式不難, 難的是測資#9一直TLE. 我原以為演算法已經夠快了, 怎麼會TLE呢? 後來終於想到如果是下面這種測資, 沒有用快速的搜尋, 就會變成非常非常慢.
100000 1 1 1 1 1 1.......1 1 1 1 1 1 1.......1
這種情況解決後, 就AC了. 記得要用 scanf和printf 還可以比cin,cout省個200ms左右.
資料結構 我把學生的資料放在RECORD裡, 裡面就是一個vector, 用來應付很多相同編號的卡片時, 需要儲存很多的index. vector在增加後面資料的速度很快,正好適用.
class RECORD {
public:
vector <int> INDEX;
void Set(int index){
INDEX.push_back(index);
}
};
RECORD student[100001];
int teacher[100000];
演算法
輸入學生資料時, 卡片編號是I, 就把index加入RECORD[I]的INDEX裡, 這樣也不用再排序student[ ], 找卡片編號的資料時也快.
for(int i=0;i<N;i++){
int I;
scanf("%d", &I);
student[I].Set(i);
}最後就是根據老師的卡片編號, 去學生的student[ ]裡找最接近的位置.
int target=teacher[i];
int C=student[target].INDEX.size();
if(C==0){ //沒有紀錄
printf("-1 ");
}else{
auto p1= student[target].INDEX.begin();
auto p2= student[target].INDEX.end();
auto lower = std::lower_bound(p1, p2 , i); //找大於或等於i的
int diff1=1000000;
int diff2=1000000;
if(lower != p2){ //有找到
diff1=*lower - i;
}
if(lower != p1){ //如果不是第一個
lower--; //找前一個
diff2=i - *lower;
}
printf("%d ",(diff1<diff2? diff1:diff2)); //誰比較小就印出誰
}完整程式如下.
#include <vector>
#include <iostream>
using namespace std;
class RECORD {
public:
vector <int> INDEX;
void Set(int index){
INDEX.push_back(index);
}
};
RECORD student[100001];
int teacher[100000];
int main() {
cout.sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N;
scanf("%d", &N);
for(int i=0;i<N;i++){
scanf("%d", &teacher[i]);
}
for(int i=0;i<N;i++){
int I;
scanf("%d", &I);
student[I].Set(i);
}
for(int i=0;i<N;i++){
int target=teacher[i];
int C=student[target].INDEX.size();
if(C==0){ //沒有紀錄
printf("-1 ");
}else{
auto p1= student[target].INDEX.begin();
auto p2= student[target].INDEX.end();
auto lower = std::lower_bound(p1, p2 , i); //找大於或等於i的
int diff1=1000000;
int diff2=1000000;
if(lower != p2){ //有找到
diff1=*lower - i;
}
if(lower != p1){ //如果不是第一個
lower--; //找前一個
diff2=i - *lower;
}
printf("%d ",(diff1<diff2? diff1:diff2)); //誰比較小就印出誰
}
}
return 0;
}
