1

配列のすべての要素間の最小の差を見つけたいです。他のさまざまな質問を読みましたが、次のコードでエラーの正確な原因を見つけることができませんでした。

#include<iostream>
#include<stdio.h>
#include<cstdlib>

using namespace std;

void quicksort(long int *lp, long int *rp);

int main()
{
    int t,n;
    long int s[5000];

    cin>>t;
    while(t--){
    cin>>n;
    for(int i=0;i<n;i++) cin>>s[i];
    quicksort(&s[0],&s[n-1]);
    //cout<<"passes:"<<passes<<endl;
    //for(int i=0;i<n;i++) cout<<s[i]<<" ";
    long int min = abs(s[1]-s[0]);
    //cout<<endl<<min;
    for(int i=1;i<(n-1);i++){
        long int temp = abs(s[i]-s[i+1]);
        if (temp <= min) min = temp;
    }
    cout<<min;
    }
}

void quicksort(long int *lp,long int *rp){
    int arraysize= (rp-lp)+1;
    if(arraysize > 1){
       long int *pivot = (lp+(arraysize/2));
       long int swap=0;
      long int *orgl = lp;
      long int *orgr = rp;
      while(lp!=rp){
        while (*lp < *pivot) lp++;
        while (*rp > *pivot) rp--;
        if (lp == pivot) pivot=rp;
        else if (rp == pivot) pivot=lp;
        swap = *lp;
        *lp = *rp;
        *rp = swap;
        if((*lp == *pivot) || ( *rp == *pivot)) break;
    }
    quicksort(orgl,pivot-1);
    quicksort(pivot+1,orgr);
}

}

問題の説明は次のリンクに記載されています：http：//www.codechef.com/problems/HORSES 私のプログラムのエラーを特定できますか？

4

4 に答える 4

3

C++ を使用しているため、実際には O(n*logn) を保証しないカスタム クイックソートを使用する代わりに、 sort from を使用することをお勧めします<algorithm>。このロジックは良さそうです:

    long int min = abs(s[1]-s[0]);
    //cout<<endl<<min;
    for(int i=1;i<(n-1);i++){
        long int temp = abs(s[i]-s[i+1]);
        if (temp <= min) min = temp;
    }

By the way: 
cout<<min; 
Add cout<<min << endl;
于 2012-09-20T04:05:15.087 に答える
0

この線

if((*lp == *pivot) || ( *rp == *pivot)) break;

間違っている。検討

5 4 7 5 2 5
      ^
    pivot

おっと。

この行

long int temp = abs(s[i]-s[i+1]);

不必要に複雑です。配列は（おそらく）ソートされているので、

long int temp = s[i+1] - s[i];

を呼び出さなくても同じことを行いabsます。

于 2012-09-20T04:09:03.340 に答える
0 
sort(s, s + n); // #include <algorithm> O(n*log n)

それ以外の場合、最小アルゴリズムのソート/検索は正しいです。ランダム化、バケットソートに基づくO（n）アルゴリズムがあります。

#include <algorithm> // sort()
#include <iostream>

int main() {
  using namespace std;
  int ntests, n;
  const int maxn = 5000; // http://www.codechef.com/problems/HORSES
  int s[maxn];
  cin >> ntests; // read number of tests
  while (ntests--) {
    cin >> n; // read number of integers
    for (int i = 0; i < n; ++i) cin >> s[i]; // read input array

    sort(s, s + n); // sort O(n*log n)
    // find minimal difference O(n)
    int mindiff = s[1] - s[0]; // minn = 2
    for (int i = 2; i < n; ++i) {
      int diff = s[i] - s[i-1];
      if (diff < mindiff) mindiff = diff;
    }
    cout << mindiff << endl;
  }
}
于 2012-09-20T04:12:44.493 に答える
0 
#include <iostream> using namespace std;

int main() {
    int a[] = {1,5,2,3,6,9};
    int c=0;
    int n = sizeof(a)/sizeof(a[0]);
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            cout<<a[i]<<" - "<<a[j]<<" = "<<a[i]-a[j]<<endl;
            if(abs(a[i]-a[j]) == 2)
                c++;
        }
    }
    cout<<c<<endl;
    return 0; }
于 2020-09-24T15:55:20.320 に答える