Re: [問題] 成績數據求最大值

看板C_and_CPP (C/C++)作者tropical72 (藍影)時間15年前 (2011/05/28 12:43)推噓4(4推 0噓 9→)

留言13則, 6人參與討論串2/2 (看更多)

恕刪姑且不論您的方法不好，但從 code http://pastie.org/1983482 底下有幾個問題是值得探討的在題目的「提示」裡面 http://judge.tnfsh.tn.edu.tw:8080/ShowProblem?problemid=a004 已有說明，必須注意不可以宣告過大的區域變數(在main裡面宣告之類的)，「否則會造成 Run Time Error」，我不知道這是不是吃 WA 的原因之一，但的確有可能，因您問題也說了，前面資料量小都正常，但資料量一大的時候就不行，這的確很可能是上述原因所造成，這種現在就叫 stack overflow。 int n,i,j; cin >> n; short grade[n+2],tmp_g=0; 這段碼可異議性應不少 a. 若真的是要存 0~100，要省空間的話可用 unsigned char/char 便可， unsigned char ch; // range: 0~255 在輸出時進行強制轉型，如 cout << (unsigned)ch; 即可，但這還是小問題 b. 上面的 short grade[n+2] 便犯了題意中所說的，宣告過大區域變數。事實上 grade 這變數在此用法為 VLA (VLA variable length array)，這應是 C99 以後才有的東西，但我非常不建議這麼用。程式在執行時，所需的資料「大致」上可分「放在 stack、放在 heap」，頂多再加一項：放在 register(這裡不談這個) 執行速度應是 register > stack > heap 而可放的數量 register < stack < heap VLA 實際上還是放在 stack 裡面，而且很糟的是，「據悉」， VLA 事實上會向 OS 要一塊比需求還要大的 stack，而且還大不小，意指沒用到的就浪費掉了。一般陣列： #define N 10 int array1[N]; int array2[10]; 扣除上面這二個，其它的都是 VLA。 cin >> N; int array1[N]; a = b + c; int array2[a]; 題意應是指，真的要這麼做就放在 heap 裡面去，C++ 裡面可用 new 去完成 cin >> N; int *array = new int[N]; // 這只是語法而已，記下來！ for(int i=0; i!=N; ++i) array[i]=i; // 存取和一般陣列沒二樣 delete [] array; // 用完後再刪除另外 C++ 比較多人推的是用 container - vector，這部份推測您應該還不知道，所以不再贅述。唯應注意的是，即使用 vector / new 方式可「盡可能」取得可用之記憶體空間，但 coder 可用之記憶體空間仍有上限，但若以題意所言，max of N = 100000，即使是用 int 去存數值，也只吃到 0.8 MB 記憶體(分數、座標)， 1MB 都不到這絕對可以正常執行。故我認為這題是要說明，若要用排序法的話，那就用動態配置記憶體方式，或許 vector container 去處理。 c. 索引值問題我沒實際跑過你的排序法 (其實也看不懂是什麼排序法, 選擇 or 泡沫？)，第一個該改善的地方，便是要習慣 C/C++ 很多東西是從 0 開始計數，而不是從 1 開始計數，要改過來最簡單的方式，就是一段時間強制規定自己， loop 裡面一律以 0 當起始值。 d. 排序問題另這題在排序時，只要排一次便可，沒必要分二次排，這樣在其它地方很可能會拿到 TLE ( Time Limit Error)，排的條件可以一次寫進去，以 select sorting 為例 for(i=0; i!=n-1; ++i){ for(j=i+1; j!=n; ++j){ if( (a[i] > a[j]) || ( (a[i]==a[j]) && score[i]<score[j] ) _ swap(a[i], a[j]), swap(score[i], score[j]); } } 這只是一點小建議，僅供參考。 -- YouLoveMe() ? LetItBe() : LetMeFree(); -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 180.177.73.222