c++ - Topcoder SRM 149 D2 Q3 : Pricing

Question

下面这个问题是从 Topcoder 的 SRM 149 中提取的。即使在看了解决方案之后，我也不知道如何做这个问题。我已经尝试这个问题一个半小时了，然后又花了一个小时来解决这个问题，但我就是无法理解它到底在做什么....

如果有人可以就此解决方案的工作原理向我提供一些提示，我将不胜感激。

问题:http://topcoder.bgcoder.com/print.php?id=250

解决方案:http://apps.topcoder.com/forums//?module=Thread&threadID=575120&start=0

SRM 149(Division II 三级)中使用的 TopCoder 问题“定价”

问题陈述最简单形式的市场差异化是一种针对同一产品向不同客户收取不同价格的系统。为了最大化总销售收入，我们希望单独向每个客​​户收费，收取该客户愿意支付的最高价格。通常我们要把顾客分成几组，对一组中的每个人收取相同的价格(例如商务舱、经济舱等)。我们有一份 list ，上面列出了我们产品的所有潜在客户以及每个客户愿意支付的最高金额。我们决定将它们分成四个或更少(不重叠)的组。每个组中的每个人都将获得相同的价格。我们的目标是选择最优的组和价格，以最大化我们的总销售收入。

创建一个包含方法 maxSales 的 Pricing 类，该方法采用包含每个潜在客户愿意支付的最高价格的 int[] 价格，并返回我们通过将客户分为四个或更少的组可以产生的最大销售收入.

定义

类:定价方法:maxSales参数:int[]返回值:整数方法签名:int maxSales(int[] price)(确保你的方法是公开的)

约束

• 价格必须包含 1 到 50 个元素(含)
• 价格的每个元素必须介于 0 和 1000 之间(含)

例子

0)

{9,1,5,5,5,5,4,8,80}返回:120向愿意支付 80 的客户收取 80。向愿意支付 8 或 9 的 2 个客户收取 8。向愿意支付 5 的 4 个客户收取 5。向愿意支付 4 的客户收取 4。总销售收入=1*80+2*8+4*5+1*4。 (我们可以将愿意支付 1 的客户放入这些组中的任何一个，因为他不会以这些价格购买任何东西。)1)

{17,50,2}返回:69我们只使用三个组，每个组包含一个客户。我们向每位顾客收取她愿意支付的最高费用。总销售收入=1*17+1*50+1*22)

{130,110,90,13,6,5,4,3,0}返回:346向愿意支付 4 到 13 的 4 位顾客中的每人收取 4 的价格，从而从他们那里总共得到 16。然后向愿意多付钱的三个客户中的每一个收取最多的费用。 4*4 + 90 + 110 + 130 = 346

SOLUTION:
Arrays.sort(price);
   int ret = 0;
   for(int i = 0; i<price.length; i++){
      for(int j = i; j<price.length; j++){
         for(int k = j; k<price.length; k++){
            for(int m = k; m<price.length; m++){
               int rev = 0;
               for(int n = 0; n<price.length; n++){
                  if(price[n]>=price[m]){
                     rev+=price[m];
                  }else if(price[n]>=price[k]){
                     rev+=price[k];
                  }else if(price[n]>=price[j]){
                     rev+=price[j];
                  }else if(price[n]>=price[i]){
                     rev+=price[i];
                  }
               }
               ret=Math.max(ret,rev);
            }
         }
      }
   }
   return ret;

Answer 1

这是蛮力。

每组 {i,j,k,m} 是四组的价格选择。 n 循环计算该选择的 yield ，ret 跟踪最大 yield 。

(这个解是O(N⁵)。我认为O(N)是可能的。)