这是我的解决方案:
#include <iostream>
using namespace std;
int main(){
unsigned long numberOfGums;
unsigned long hardnessLimit;
unsigned long counter = 0;
cin >> numberOfGums;
cin >> hardnessLimit;
unsigned long gums[numberOfGums];
for(unsigned long i=0; i<numberOfGums; i++){
cin >> gums[i];
}
for(unsigned long i=0; i<numberOfGums; i++){
if(gums[i] < hardnessLimit){
for(unsigned long j=i+1; j<numberOfGums; j++){
if((gums[i] + gums[j]) < hardnessLimit){
counter++;
}
}
}
}
cout << counter << endl;
return 0;
}
这个程序给我 TLE(Time Limit Exceeded) 错误,因此我只得到 30 分(满分 100 分)。具体来说,这个程序无法完成 子任务-2 值得剩下的 70 分(在问题页面上给出)。
我尝试过使用 printf 和 scanf 而不是 cin 和 cout,但程序仍然不够快。
我可以做些什么来改进这个程序,或者什么是解决这个问题的更好方法。
我也试过了,但得到了同样的错误:
#include <iostream>
using namespace std;
int main(){
long numberOfGums;
long hardnessLimit;
long counter = 0;
long temp = 0;
cin >> numberOfGums;
cin >> hardnessLimit;
long gums[numberOfGums];
for(long i=0; i<numberOfGums; i++){
cin >> temp;
if(temp < hardnessLimit){
gums[i] = temp;
}
}
for(long i=0; i<numberOfGums; i++){
if(gums[i] != -1){
for(long j=i+1; (j<numberOfGums); j++){
if(((gums[i] + gums[j]) < hardnessLimit) && gums[j] != -1){
counter++;
}
}
}
}
cout << counter << endl;
return 0;
}
最佳答案
您的解决方案是 O(N^2)
,它肯定会在给定约束的情况下超时。
更有效的解决方案是 O(NlogN)
解决方案。这是算法的基本轮廓:
对数组进行排序。这需要
O(NlogN)
时间。现在对于排序数组中的每个元素,比如
p
,在数组中搜索元素索引(元素p
的右侧),使得该索引处的值小于k - p
。为此使用二进制搜索。找到这个索引后,您可以很容易地计算出与元素p
关联的此类对的数量。对于每个元素,此完整步骤花费O(logN)
时间对数组中除最后一个元素之外的所有元素执行上述过程,因为它的右边没有左边的数组。
您将通过对您获得的每个元素 p
的所有对求和来得到答案
希望对您有所帮助!!!
编辑:我正在添加上述算法的 C++ 实现。该解决方案通过了 CodeChef 上的所有测试用例。
#include <iostream>
#include <algorithm>
using namespace std;
int binsearch(int a[],int n, int x)
{
int low, high, mid, k=-1;
low = 0;
high = n-1;
while(low<=high)
{
mid = (low+high)/2;
if(a[mid] <= x-1){
k = mid;
low = mid+1;
}
else{
high = mid-1;
}
}
return k;
}
int main()
{
int n, k, i, j;
long long ans = 0;
cin>>n>>k;
int arr[n];
for(i=0;i<n;i++)
{
cin>>arr[i];
}
sort(arr,arr+n);
j = 0;
while(j<n-1)
{
if(k-arr[j] > 0)
{
int ind = binsearch(arr,n,k-arr[j]);
ans = ans + (ind-j>=0 ? (ind-j):0);
}
j++;
}
cout<<ans<<endl;
return 0;
}
关于c++ - CodeChef 上的时间限制错误,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40417943/