→ adrianshum:b 大太好人了, 這種作業文我看到只想噓... 03/10 15:30
推 ohya0524:感謝bleed1979大的幫忙 還有這不是作業...單純衝題數 03/10 17:17
→ adrianshum:作業文不是單指作業. 只丟個問題出來又沒有更多資料, 03/11 14:30
→ adrianshum:只叫別人幫你做人肉debugger, 就已經是十足的作業文了 03/11 14:30
其實你可以大概說一下你的解法如何，這樣看code的人會比較快進入狀況。
所以我由模糊到清晰提供你3個面向的思考模式，
你可以每在一個面向後就回頭改你的code。。
[1]解法思考
題目規定要找大於高度的最小，和小於高度的最大。
相等是不可以的，且相等可能不止一個。
所以可以挑其中一個先做。
我的作法是先找大於高度的最小，在利用索引值回頭找小於高度的最大。
一樣是二元搜尋。
[2]程式架構和代碼
如果你遵照[1]的解法還是無法AC，這裡是程式架構，再送你一個二元搜尋的代碼。
二元搜尋︰
unsigned int binary_search(const vector<unsigned int> &A,
unsigned int left, unsigned int right,
const unsigned int &N,
unsigned int value)
{
if (left < right)
{
int mid = (left + right) >> 1;
if (A[mid] == value)
return(mid);
else if (A[mid] < value)
return(binary_search(A, mid + 1, right, N, value));
else
return(binary_search(A, left, mid - 1, N, value));
}
if (left != N && A[left] < value)
return(left + 1);
return(left);
}
你可以看到這個二元搜尋的代碼傳入一個N值，用以判斷找不到大於高度的最小的情況。
找不到要傳回N，包含在回傳left + 1的情況。
程式架構︰
unsigned int N; // N 個母猴
/**
這邊請先把所有母猴的高度讀入
**/
int Q; // Q個要搜尋的公猴
while (Q--)
{
unsigned int height; // 公猴的高度
unsigned int i = binary_search(chimps, 0, N, N, height);
// 二元搜尋︰結果為大於高度的最小的索引值存在i，
// 有可能在索引值i的高度是相等的。
// 一個for迴圈，如果高度相等要往後找大於高度的最小，視情況i是否遞增
if (i < N) // 如果母猴之中有比公猴高度還高的情況
{
int j;
// 一個for迴圈，往前找小於公猴高度的最大
if (j >= 0)
// 如果找得到小於公猴高度的最大要怎麼輸出
else
// 如果找不到又怎麼輸出
}
else // 如果母猴之中沒有比公猴高度還高的情況
{
int j;
// 一個for迴圈，從索引值從N - 1往前找是否有小於公猴高度的最大
if (j >= 0)
// 如果找得到小於公猴高度的最大要怎麼輸出
else
// 如果找不到又怎麼輸出
}
}
[3]完整程式碼
http://codepad.org/w3DodMno
程式架構的實踐，僅供參考。
Bleed
※ 引述《ohya0524 (歐爺)》之銘言：
: ( *[1m *[m 為色碼，可以按 Ctrl+V 預覽會顯示的顏色 )
: ( 未必需要依照此格式，文章條理清楚即可 )
: 題號： 10611 題目:
: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1552
: 遇到的問題： WA...
: 有問題的code： (請善用置底文的標色功能)
: #include<stdio.h>
: #include<stdlib.h>
: int bsearch(int *a,int l,int r,int key)
: {
: while(l<r)
: {
: int mid=(l+r)/2;
: if(key==a[mid]) return mid;
: else if(key>a[mid]) l=mid+1;
: else r=mid-1;
: }
: if(a[l]>key) return l;
: else return l+1;
: }
: int main()
: {
: int N,Q,*h1,*h2,i,j,result,middle,time=0;
: scanf("%d",&N);
: h1=(int*)malloc(sizeof(int)*N);
: for(i=0;time!=N;i++)
: {
: scanf("%d",&h1[i]); time++;
: if(h1[i]==h1[i-1])
: i--;
: }
: N=i;
: scanf("%d",&Q);
: h2=(int*)malloc(sizeof(int)*Q);
: for(i=0;i<Q;i++)
: scanf("%d",&h2[i]);
: for(i=0;i<Q;i++)
: {
: if(h2[i]>h1[N-1]) printf("%d X\n",h1[N-1]);
: else if(h2[i]<h1[0]) printf("X %d\n",h1[0]);
: else if(h2[i]==h1[N-1])
: {
: if(N-2>=0)
: printf("%d X\n",h1[N-2]);
: else
: printf("X X\n");
: }
: else if(h2[i]==h1[0])
: {
: printf("X %d\n",h1[1]);
: }
: else
: {
: result=bsearch(h1,0,N-1,h2[i]);
: if(h1[result]==h2[i]) printf("%d %d\n",h1[result-1],h1[result+1]);
: else printf("%d %d\n",h1[result-1],h1[result]);
: }
: }
: system("pause");
: return 0;
: }
: 補充說明：
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.32.177.97
※ 編輯: bleed1979 來自: 114.32.177.97 (03/10 07:57)