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

[tropical72 (藍影)]

恕刪
姑且不論您的方法不好，但從 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
→ firejox:我覺得數據這麼大就不要用O(n^2)的sort了...
→ tropical72:單純沒想到哪個 nlogn sorting 適合和初學者說明的 XD
推 littleshan:求最大值而已 不需要sort啊！
→ littleshan:另外heap是配置比較花時間，存取效率和stack相同
推 cory8249:非常感謝大大的詳細解說與建議    我原本的跑法確實會TLE
推 shec1213:求單一最大值只需要O(n) 不過這題還要考慮同分的問題
→ tropical72:@littleshan,我只是單純把原po的東西拉出來探討而已.
推 NlA:要是只要求最大值 其實做一個while(N>0) 去比較前後輸入的數
→ NlA:比較大的數先留存下來 題目有說用不到陣列的方法
→ NlA:或許可以試試看這方法 小弟拙見
→ tropical72:@NIA:我於原帖有提供非陣列解,這只是純粹探討原po寫法.
→ NlA:恩 SORRY 一開始沒注意看 事後才看到
→ firejox:其實可以用O(n)的sort來解釋XD