2

InterviewStreet の課題「Flowers」を解決しています。

あなたとあなたの K-1 の友達は、N 個の花を買いたいと思っています。花番号 i は寄主 ci を持っています。残念ながら、売り手は顧客がたくさんの花を買うのを好まないので、以前に花を購入した顧客のために花の価格を変更しようとしました。より正確には、顧客がすでに x 個の花を購入している場合、花番号 i を購入するには (x+1)*ci ドルを支払う必要があります。

あなたとあなたの K-1 の友人は、できるだけお金を使わないように N 個の花をすべて購入したいと考えています。

しかし、私のソリューションはテスト ケース 3、5、および 7 に失敗しているため、スコアは 7/10 です。

私はすでに自分のコードを徹底的にテストしており、常に正しい回答が得られているため、この課題でフルスコアを取得できない理由がわかりません.

基本的に私がしていることは、購入する花よりも多くの友人がいる場合、花の価格の合計を返すということです.

購入する花が友人よりも多い場合は、花の価格を降順 (高いものから安いものへ) に並べ替え、友人に 1 つずつ購入させます。

typedef unsigned long long int uint64;
uiRemainder = n % k;

    sort(viFlowersCost.begin(), viFlowersCost.end(), greater<int>()); //Sorted Array Descending

    if(uiRemainder == 0) {
            for(a = 0; a < n; a+=k) {
                    for(b = 0; b < k; ++b) {
                            ui64Result += (x+1)*viFlowersCost[a+b];
                    }
            ++x;
            }
    } else {
            for(a = 0; a < (n/k)*k; a+=k) {
                    for(b = 0; b < k; ++b) {
                            ui64Result += (x+1)*viFlowersCost[a+b];
                    }   
                    ++x;
            }   
            for(b = 0; b <= uiRemainder; ++b) {
                    ui64Result += (x+1)*viFlowersCost[a+b];
            }   
    }   

    cout<<ui64Result;

私の質問は、次の制約が与えられた場合、どの入力が私のプログラムに間違った答えをスローさせるかということです:

制約 :

1 <= N、K <= 100

各花は1,000,000以下の費用がかかります

私はすでに極端なケースについてテストしました：

N = 99 K = 100 で、100 個の花が 900,000 ～ 1,000,000 の範囲の価格で続きますが、それでも正しい答えが得られます。

たとえば、次のテスト ケース:

99 100

916807 972425 933847 933809 997490 906570 926534 936300 963336 917637 956205 927011 966648 942300 906839 911128 967915 931564 970607 941177 935338 918421 905061 977177 911389 959618 991125 966236 942883 980278 979549 991459 907876 928248 908003 970585 967394 962906 915297 950976 906662 989573 985875 903158 911494 990185 911664 975093 934338 976986 918541 910894 911602 952041 907953 967915 977677 982920 990006 959603 908295 943832 917462 911173 976614 996246 935262 945460 987876 973350 949546 930732 922685 988390 912489 979841 918856 953461 923072 985130 906338 917402 975289 931717 927872 920676 914295 994827 997989 975217 977181 914545 991968 935860 994059 913399 927867 912266 948655 944224

私のプログラムの出力：

93697342

インタビュー通りで正解はどれ?

4

0 に答える 0