文章出處
文章列表
序言（廢話）
今天做鏈家網的筆試題， 選擇題考的好雜好雜啊， php, java, C++ 幾乎是等比重的考察，完全沒有側重，完全沒有側重。 幸虧都是基本語法， 大部分只要用心猜（反正編程語言都差不多了，畢竟咱是學C++的， 什么邪惡的寫法沒見過~~~~）。
然后是筆試題， 其實筆試題三道都挺簡單的， 只不過第三道題會卡時間。
題目描述
小恪要給學校里的人分組， 每個人的編號是連續的正整數（從1開始）。 然后根據某些同學的編號，查詢它在哪個組里。
輸入描述
第一行輸入正整數 n， 代表總共有幾數, 然后下一行輸入 n 個正整數，表示每一個組有幾個成員。
第三行輸入正整數m, 代表有 m 次的詢問。 然后下一行有 m 個正整數, 表示詢問編號為 Mi的成員，在哪一組？
5
2 7 3 4 9
3
1 25 11題目輸出
1
5
3數據范圍
1<= N <= 10^5, 1<= 每個組的成員數量 <= 10^6, 1<= M <= 10^5.
解題代碼
方法一： 直接做
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <stdexcept>
using namespace std;
const int maxn = 100000 + 5;
long long arr[maxn];
long long brr[maxn];
int main()
{
int n;
cin >> n;
arr[0] = 0;
for(int i = 1; i <= n; i++)
cin >> arr[i];
for(int i = 2; i <= n; i++)
arr[i] = arr[i] + arr[i-1];
int m;
cin >> m;
for(int i = 1; i <= m; i++)
cin >> brr[i];
for(int i = 1; i <= m; i++)
{
for(int j = 1; j <= n; j++)
{
if(arr[j] >= brr[i])
{
cout << j << endl;
break;
}
}
}
return 0;
}在規定的時間內，通過了 82%樣例。 也就是說稍微有些超時~~~
方法二： 用二分查找代替順序查找
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
const int maxn = 100000 + 5;
long long arr[maxn];
long long brr[maxn];
int bSearch(long long arr[], int left, int right, long long val)
{
while(left < right)
{
int mid = left + (right - left)/2;
if(arr[mid] < val)
left = mid+1;
else if(arr[mid] > val)
right = mid;
else
return mid;
}
return left;
}
int main()
{
int n;
cin >> n;
arr[0] = 0;
for(int i = 1; i <= n; i++)
cin >> arr[i];
for(int i = 2; i <= n; i++)
arr[i] = arr[i] + arr[i-1];
int m;
cin >> m;
for(int i = 1; i <= m; i++)
cin >> brr[i];
for(int i = 1; i <= m; i++)
{
cout << bSearch(arr, 1, n+1, brr[i]) << endl;
}
return 0;
}然而結果仍然是 82%， 好坑啊， 數據好沒區分度啊！！！, 本來以為這種程度的優化絕壁就能過了， 于是就沒打算寫下面的第三種方法，結果。。。。悲劇了！！！！
方法三： 空間換時間， 排序+hash
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
using namespace std;
const int maxn = 100000 + 5;
long long arr[maxn];
long long brr[maxn];
long long crr[maxn];
int main()
{
int n;
cin >> n;
arr[0] = 0;
for(int i = 1; i <= n; i++)
cin >> arr[i];
for(int i = 2; i <= n; i++)
arr[i] = arr[i] + arr[i-1];
int m;
cin >> m;
for(int i = 1; i <= m; i++)
{
cin >> brr[i];
crr[i] = brr[i];
}
unordered_map<long long, long long> mm;
sort(crr+1, crr+m+1);
int pos = 1;
int i = 1;
while(i <= n)
{
if(pos > m)
break;
while(arr[i] < crr[pos])
i++;
mm[crr[pos]] = i;
pos++;
}
for(int i = 1; i <= m; i++)
cout << mm[brr[i]] << endl;
return 0;
}毫無疑問， 這個提交絕不會超時，因為時間復雜度是O(NlogN)啊， 并且沒有常數因子， 線段樹也只能是這樣的復雜度了吖。 但是， 但是， 鏈家網用的筆試OJ好差啊， 提交一個題目要十分鐘 ~ ~ 。
聽說由于這個原因， 最后延時半小時 ~ ~ ~， 可是我已經提前交卷了， ~ ~ ~， 感覺好坑啊。 （當然主要還是怪自己沒有再等等 ~ ~ ~）。 寫篇博客，總結一下教訓，不喜勿噴~~。
文章列表
全站熱搜
留言列表
