#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 的倍數。
以上,希望有幫助到您。