4

質問: 2n 個の整数の配列が与えられます。この整数の配列の各ペアは、それぞれ恐竜の誕生年と死亡年を表します。考慮したい有効な年の範囲は [-100000 から 2005] です。たとえば、入力が次の場合:

-80000 -79950 20 70 22 60 58 65 1950 2004

これは、最初の恐竜の誕生年が -80000 年で、死亡年が -79950 年であることを意味します。同様に、2 番目の恐竜は 20 歳から 70 歳まで生きました。

かつて生きていた恐竜の最大数を知りたい. 上記の 2n 整数の配列が与えられた場合に、これを計算するメソッドを作成します。

誰でも解決策を見つける方法を提案できますか?

これで試した編集→ラフコード

#include<stdio.h>
#include<stdlib.h>
#include <stddef.h>
static void insertion_sort(int *a, const size_t n) {
    size_t i, j;
    int value;
    for (i = 1; i < n; i++) {
        value = a[i];
        for (j = i; j > 0 && value < a[j - 1]; j--) {
            a[j] = a[j - 1];
        }
        a[j] = value;
    }
}


int  main(){
    int arr[10]={-80000,-79950,20,70,22,60,58,65,1950,2004};
    int strt[5],end[5];
    int bal[5];
     int i,j,k,l,m,length;
     l=0;
     m=0;
   for (i=0; i<10; i++){
       //printf("i = %2d arr[i] = %2d\n", i, arr[i]);
       if(i%2==0){
       strt[l]=arr[i];
       l++;
       }else{
       end[m]=arr[i];
       m++;
       }
   }
   insertion_sort(strt, sizeof strt / sizeof strt[0]);
   insertion_sort(end, sizeof end / sizeof end[0]);
   k=sizeof(end)/sizeof(int);
   for(j=0;j<5;j++){
       bal[i]=strt[i]-end[k-1];
       k--;

   }
   length=sizeof bal / sizeof bal[0];
   insertion_sort(bal, sizeof bal / sizeof bal[0]);
   printf("answer is = %2d",bal[length-1]);

}

しかし、出力は期待どおりではありません。私が見逃していることを教えてください。

4

5 に答える 5

14

それぞれの恐竜の誕生を開き括弧と見なし、死を閉じ括弧と見なします。次に、括弧を日付で並べ替えます。これにより、出生と死亡のすべてのイベントの時系列順になります。その後、括弧シーケンスを通過し、バランスを計算します（'（'でインクリメントし、'）'でデクリメントします。最大バランスを追跡し、それが答えになります。

アップデート：

C++のサンプルソース。
入力：恐竜の数n、次に2nの生年月日と死亡日。
出力：同時に生きている恐竜の最大量の数

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<pair<int, int> > dinos(2*n); // <date, died/born>
    int i;
    for( i = 0; i < n; ++i )
    {
        cin >> dinos[ 2 * i ].first >> dinos[ 2 * i + 1 ].first;
        dinos[ 2 * i ].second = 1; // born
        dinos[ 2 * i + 1 ].second = 0; // died
    }
    sort( dinos.begin(), dinos.end()); // sorts by date first
    int ans = 0, balance = 0;
    for( i = 0; i < dinos.size(); ++i )
        if( dinos[ i ].second ) // someone's born
        {
            ++balance;
            ans = max( ans, balance ); // check for max
        }
        else
            --balance;
    cout << ans << endl;
    return 0;
}

PS私は、2つのディノが同時に生まれて死んだ場合、それらは一緒に住んでいないと思いました。反対の場合は、値をborn = 0、died=1に変更するだけです。

于 2013-02-01T12:57:25.540 に答える
3 
Largest number of dinosaurs that were ever alive at one time?

これはjavaのサンプル ソース コードです。

入力: 恐竜の数 n、生年月日 n、死亡日 n。

出力: かつて生きていた恐竜の最大数

import java.util.Arrays;

public class Dinosaur {

   public static void main(String args[]) {
        int birthAndDeath[] = { -80000, -79950, 20, 70, 22, 60, 58, 65, 1950, 2004};
        System.out.print("Maximum number of dinosaurs that were ever alive at one time: " + new Dinosaur().findMaxdinosaur(birthAndDeath));
    }

   /**
    * Find the Maximum number of dinosaurs that were ever alive at one time.
    * @param years
    * @return maximum number of dinosaurs that were ever alive at one time.
    */
   public int findMaxdinosaur (int[] years) {
        /** For birth array */
        int birthArray[] = new int [years.length/2];

        /** For death array */
        int deathArray[] = new int [years.length/2]; 

        int birthCounter = 0, deathCounter = 0;
        int currentAliveDinos = 0;

        /** Maximum number of dinosaurs that were ever alive at one time. */
        int maxDinos = 0; 

        int position = 0;

        /** To get the birth and death values in different array */
        for(int index = 0; index < years.length; index = index + 2) {
            birthArray[position] = years[index];
            deathArray[position] = years[index + 1];
            position++;
        }       

        /** Sort the birth and death array in ascending order. */
        Arrays.sort(birthArray);
        Arrays.sort(deathArray);

        /** Calculating max number of dinosaurs that were ever alive at one time **/
        while( birthCounter != years.length/2 && deathCounter != years.length/2) {
            if(birthArray[birthCounter] < deathArray[deathCounter]) {
                currentAliveDinos++;
                birthCounter++;
            } else {
                currentAliveDinos--;
                deathCounter++;
            }
            if(maxDinos < currentAliveDinos) {
                maxDinos = currentAliveDinos;
            }
        }
        return maxDinos;
   }
}
于 2013-02-04T19:10:25.170 に答える
2

という構造体を作成し、DinosaurEvent1 年 (イベントが発生した年) とイベントの種類 (誕生または死亡) を格納します。独自の比較関数を実装して、qsort に渡して、年に応じて最初の並べ替えを行います (死亡が出産の前に発生した場合、またはその逆の場合を考慮してください。つまり、どちらかの端に含まれる範囲です) 与えられた配列を反復処理します。すべてのイベントをベクトルに入れます。その後、ベクターをソートし、イベントを順番に処理します。特定の年のすべてのイベントを同時に処理し (またはステートメントに応じて出生または死亡のみ)、現在生きている恐竜の数を再計算します (出生が 1 増加すると死亡が 1 減少します)。常に最大値を保存すると、これが答えになります。それが理にかなっていることを願っています。

解決策全体を提供して申し訳ありませんが、実際にすべてを言わずにヒントを与える方法がわかりませんでした。

于 2013-02-01T12:55:05.387 に答える
1 
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{

unsigned int n;
cin >> n;
vector<pair<int, int> > dinos(2*n); // <date, died/born>

unsigned int i;
for( i = 0; i < n; ++i )
{
cin >> dinos[ 2 * i ].first >> dinos[ 2 * i + 1 ].first;
dinos[ 2 * i ].second = 1; // born
dinos[ 2 * i + 1 ].second = 0; // died
}

sort( dinos.begin(), dinos.end()); // sorts by date first
int ans = 0, balance = 0;

for( i = 0; i < dinos.size(); ++i ) {
if( dinos[ i ].second ) // someone's born
{
++balance;
ans = max( ans, balance ); // check for max
} else
--balance;
}
cout << ans << endl;
return 0;
}
于 2013-02-02T09:19:10.560 に答える