【解決方法】! コードで MLE を解決する方法!

プログラミングQA


こんな質問を見つけました。

農場主ジョンの牛はかなりの甘党で、特にキャンディケインを食べるのが大好きです。 FJ には合計 N 頭の牛がおり、それぞれが特定の初期身長を持っており、それぞれの身長も異なる (1≤N,M≤2⋅10^5) M 個のキャンディケインを彼らに与えたいと考えています。
FJ は、入力で指定された順序でキャンディーケーンを 1 つずつ牛に与える予定です。 牛にキャンディケインを与えるために、最初はキャンディケインがちょうど地面に触れるようにキャンディケインを吊り下げます。 次に、牛は入力で指定された順序で 1 頭ずつ整列し、キャンディケインに上がり、それぞれが自分の身長まで食べます (これ以上高くなることはできないため)。 キャンディケインは、牛がキャンディケインの底を食べた後でも、最初に設置された場所に吊り下げられたままで、地面に降ろされません。 キャンディケインの根元がすでに牛の高さを超えている場合、牛は自分の番の間に何も食べない可能性があります。 すべての牛が順番を終えた後、牛は食べたキャンディーケーンの数だけ身長が伸び、農夫のジョンが次のキャンディーケーンを吊るすと、牛たちは再び同じプロセスを繰り返します(再び牛1が最初にキャンディーケーンを食べ始めます)次はキャンディケーン)。 特記事項: キャンディケインは空中に浮いています。たとえば、高さ 2 の牛が高さ 3 のキャンディケインに到達すると、牛は 2 つのユニット (1 と 2) を食べ、3 番目のユニットのキャンディケインを食べます。まだ空中に浮いているので、身長が2以上の牛だけがそれを食べることができます。

入力フォーマット (パイプ標準入力):
最初の行には N と M が含まれています。
次の行には、Ncow の初期の高さが含まれており、それぞれの範囲内にあります。 [1,10^9]。
次の行には、M 個のキャンディー ケーンの高さが含まれており、それぞれの範囲内です。 [1,10^9]。

出力形式 (パイプ標準出力):
N 頭の牛それぞれの最終的な身長を別々の行に表示します。
この問題に関係する整数のサイズが大きいため、64 ビット整数データ型 (C/C++ の「long long」など) の使用が必要になる場合があることに注意してください。

入力例:
3 2
3 2 5
6 1
サンプル出力:
7
2
7 説明:
最初のキャンディケインの高さは 6 ユニットです。
1. 最初の牛は最初のキャンディーケーンの高さ 3 までの部分を食べ、その後、最初のキャンディーケーンの残りの部分が高さを占めます。 [3,6]。
2. 2 番目の牛は、最初のキャンディケインの残りの部分を食べるのに十分な身長がありません。
3. 3 番目の牛は、最初のキャンディケインをさらに 2 単位食べます。 最初のキャンディケインの残りの部分、高さを占めています [5,6]、食べられません。
次に、牛は食べた分だけ成長するので、牛の身長は [3+3,2+0,5+2]=[6,2,7]。
2 番目のキャンディケインの高さは 1 単位で、最初の牛がそれをすべて食べます。

得点:

* 入力 2 ~ 10: N,M≤10^3
* 入力 11 ~ 14: 追加の制約はありません。

そして、これが私のC++の答えです。

C++
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll n,m;
    cin>>n>>m;
    ll heightcow[n];
    for(int i=1;i<=n;i++){
        cin>>heightcow[i];
    }
    ll finalcow[n];
    for(ll i=1;i<=n;i++){
        finalcow[i]=heightcow[i];
    }
    ll heightcane[m];
    for(ll i=1;i<=m;i++){
        cin>>heightcane[i];
    }
    for(ll j=1;j<=m;j++){//cane
        bool statcane[m];
        for(ll i=1;i<=heightcane[j];i++){
            statcane[i]=true;
        }
        for(ll i=1;i<=n;i++){//cow
            for(ll k=1;k<=heightcow[i];k++){
                if(statcane[k]==true){
                    statcane[k]=false;
                    finalcow[i]++;
                }
            }
        }
    }
    for(ll i=1;i<=n;i++){
        cout<<finalcow[i]<<endl;
    }
    return 0;
}

私が試したこと:

初心者なので何をすればいいのか分かりません。 助けてください!

解決策 1

このコードで最初に気づくのは、スライスが配列の末尾を超えて拡張されていることです。

C++
ll heightcow[n] = { 3, 2, 5 };
ll heightcane[m] = { 6, 1 };
ll finalcow[n];

for (ll i = 1; i <= n; i++) {
    finalcow[i] = heightcow[i];
}

配列は常に 0 で始まり、n-1 で終わります。

コメント

タイトルとURLをコピーしました