#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?(這是什麼?)
通過檢測
terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_alloc Aborted (core dumped)
_
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 的倍數。
以上,希望有幫助到您。