2

我在 InterviewStreet 解决挑战“鲜花”：

你和你的 K-1 朋友想买 N 朵花。花号 i 有宿主 ci。不幸的是，卖家不喜欢客户购买大量鲜花，因此他试图为之前购买过鲜花的客户更改鲜花价格。更准确地说，如果客户已经购买了 x 朵花，他应该支付 (x+1)*ci 美元来购买第 i 朵花。

您和您的 K-1 朋友想要以尽可能少的钱购买所有 N 朵花的方式。

但我的解决方案未能通过测试用例：3、5 和 7，所以我的得分为 7/10。

我已经彻底测试了我的代码，它一直在给我正确的答案，所以我不明白为什么我没有在这个挑战中获得满分。

基本上我的做法是，如果买花的朋友多或相等，我会退还花的价格总和。

如果要买的花比朋友多，那么我会按降序（从贵到便宜）对鲜花的价格进行排序，让朋友一次买一朵。

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