amazon ng 凉了

和楼主一模一样的情况。。昨晚做的，我用的也是priorityqueue，然后两个sample cases过了，但是其他是0/20。。 感觉对题目理解并没有问题，debug半天都不知道为什么剩下20个test cases一个都没过

这题思路应该是先排序，然后（最大-第二大）*1+（第二大-第三大）*2 +.... 等等，加到够了他那个采购量为止

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

题是贪心，但是米不够也不知道发生了什么...

请问楼主这个解法过不了 是因为超时了么
看了看楼主的解法 while里头套了一个for和一个while，是不是因为这个超时了呀？
感觉只要一个while就可以解决问题

zxcarrot1 发表于 2020-8-21 03:06
第二题我run的时候出现 TLE， 过了一会儿， 同样的代码再次run， 又没有问题了。 虽然看不到楼主代码，感觉 ...

请问你怎么知道有tle呢？有提示么？

但是amazon今年是不是只要有oa就一定是OA123全给啊？我看它最后提交时说下一个多久之内没收到就联系他们，那这样应该就是全会给吧

剛做完OA2，兩小時就收到OA3。
估計是今天或明天開始發OA3吧
求米求米

1.    
   
2. public static void main(String[] args) {
   
3. 
   
4.         MaximumProfitForSellingAmazonBasicsProduct m = new MaximumProfitForSellingAmazonBasicsProduct();
   
5.         int numSuppliers = 2;
   
6.         int[] inventory = {3, 5};
   
7.         int order = 6; // 19
   
8. 
   
9.         System.out.println(m.calculateHighestProfit(numSuppliers, inventory, order));
   
10. 
    
11.         // ------------------------------------------------------------------------------
    
12. 
    
13.         int numSuppliers2 = 5;
    
14.         int[] inventory2 = {2, 8, 4, 10, 6};
    
15.         int order2 = 20; // 110
    
16. 
    
17.         System.out.println(m.calculateHighestProfit(numSuppliers2, inventory2, order2));
    
18. 
    
19.         // ------------------------------------------------------------------------------
    
20. 
    
21.         Random rand = new Random();
    
22.         int numSuppliers3 = rand.nextInt(50000 - 1) + 1;
    
23.         int[] inventory3 = new int[numSuppliers];
    
24. 
    
25.         int sumOfInventory = 0;
    
26.         for (int i = 0; i < numSuppliers; i++) {
    
27. 
    
28.             inventory3[i] = rand.nextInt(50000 - 1) + 1;
    
29.             sumOfInventory += inventory3[i];
    
30.         }
    
31.         int order3 = rand.nextInt(sumOfInventory - 1) + 1;
    
32.         System.out.println("sumOfInventory: " + sumOfInventory);
    
33.         System.out.println("order: " + order3);
    
34. 
    
35.         System.out.println(m.calculateHighestProfit(numSuppliers3, inventory3, order3));
    
36.     }
    
37. 
    
38. 
    
39.     // O(nlogn) + O(n) = O(nlogn)
    
40.     private static long calculateHighestProfit(int numSuppliers, int[] inventory, int order) {
    
41.         long profit = 0;
    
42.         if (numSuppliers * order == 0) return profit;
    
43. 
    
44.         Arrays.sort(inventory);
    
45. 
    
46.         int i = inventory.length - 1;
    
47. 
    
48.         while (i >= 0 && order > 0) {
    
49.             if (i == 0) {
    
50.                 while (order > 0) {
    
51.                     if (order >= (numSuppliers - i)) {
    
52.                         profit += (numSuppliers - i) * inventory[i];
    
53.                         inventory[i]--;
    
54.                         order -= (numSuppliers - i);
    
55.                     } else {
    
56.                         profit += order * inventory[i];
    
57.                         order -= order;
    
58.                     }
    
59.                 }
    
60.             } else {
    
61.                 int largest = inventory[i];
    
62.                 int second_largest = inventory[i - 1];
    
63.                 int numOfOrder = largest - second_largest;
    
64. 
    
65.                 if (numOfOrder < order) {
    
66.                     // for i < j, x = i + (i+1) + (i+2) + ... + j
    
67.                     // Gauss formula = (n / 2 + 1) * (1st num + last num)
    
68.                     double x = (((double) largest - (second_largest + 1) + 1) / 2) * ((second_largest + 1) + largest);
    
69.                     profit += x * (numSuppliers - i);
    
70.                     order -= numOfOrder * (numSuppliers - i);
    
71.                     i--;
    
72.                 }
    
73.             }
    
74. 
    
75.         }
    
76. 
    
77.         return profit;
    
78.     }

复制代码

我尝试了一下O(nlogn)，你们帮我看看有没有做错。。。[/i][/i][/i][/i][/i][/i]