#18957: 為什麼會如此?


c0745077 (Haha)

學校 : 不指定學校
編號 : 81434
來源 : [218.173.41.87]
最後登入時間 :
2022-07-16 22:21:52
e169. 粉絲入坑 - V Live & 飯拍影片 -- 트와이스 | From: [114.40.25.202] | 發表日期 : 2019-08-17 22:43

#include <iostream>
#include <bits/stdc++.h>

using namespace std;
#include <vector>
int vecscore(int*, int );
int main()
{
   std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std:: cout.tie(0);
    int n=0;
    int *score;
    while (cin>>n && n!=0){
        score= new int [n];
        for(int i=0; i<n; i++)
        {
            cin>>score[i];
        }
        cout<<vecscore(score, n)<<endl;
        delete [] score;
    }

    return 0;
}
int vecscore(int* a, int b)
{
vector <int> sum_of_score;
vector <int> :: iterator its;
    int add=0;
    int cnt=0;
    for(int i=0; i<b; i++)
    {
        for(int j=i+1; j<b; j++)
        {
            add=a[i]+a[j];
            sum_of_score.push_back(add);
        }
    }
    for(its=sum_of_score.begin(); its!=sum_of_score.end(); its++)
    {
        if(*its%100==0){
            cnt++;
        }
    }

    return cnt ;

}
測試 AC
但為什麼#1 會MLE?(這是什麼?)

#0: 50% AC (6ms, 5.1MB)

通過檢測

#1: 50% MLE (64.6MB)

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
Aborted (core dumped)
Close
_
 
#18958: Re:為什麼會如此?


inversion (「我們所認識的可符香是個像天使的好女孩」之葉林 *Cries...)

學校 : 國立清華大學
編號 : 43537
來源 : [49.159.6.107]
最後登入時間 :
2022-05-28 19:29:12
e169. 粉絲入坑 - V Live & 飯拍影片 -- 트와이스 | From: [49.158.83.43] | 發表日期 : 2019-08-17 23:05

MLE,即 Memory Limit Exceed ,表示程序執行超過記憶體限制。

而本題的記憶體限制為 64 MB 。

 

您的做法會產生出 O(n ^ 2) 的空間,也就是數量最多大約可以到 50000 × 49999 ÷ 2 個數字(因為 n 最大為 50000)存在 vector 裡。

一個 int 變數大小為 4 bytes ,所以大約會產生出 4 × 50000 × 49999 ÷ 2 ≒ 4.65 GB > 64 MB 。

因此基本上很容易就會超出限制。

 

現在的作法除了會超過記憶體限制,八成也會超過時間限制。因此,可以想想看有無其他的作法。

提示:怎樣挑才會使兩部影片的總和為 100 的倍數。

 

以上,希望有幫助到您。

 
ZeroJudge Forum