从集合 SSS 中取出 mmm 对数，使得“每对数的差的平方”之和最大，这个最大值就称为集合 SSS 的“校验值”，现在给定一个长度为 nnn 的数列 PPP 以及一个整数 kkk，我们要把数列PPP 分成若干段，使得每一段的“校验值”都不超过kkk，求最少需要分成几段，Advanced CPU Manufacturer is one of the best CPU manufacturer in the world. Every day, they manufacture n CPU chips and sell them all over the world.Given the absolute performance of the n chips P1 ...Pnmesured by ACM in order of manufacture, your task is to determine the minimum number of batches to ensure that all chips pass the test. The RPD of two CPU chips equals to the difference of their absolute performance.
给定一个整数 mmm。对于任意一个整数集合 SSS，定义“校验值”如下: 从集合 SSS 中取出 mmm 对数(即 2×m2times m2×m 个数，不能重复使用集合中的数，如果 SSS 中的整数不够 mmm 对，则取到不能取为止)，使得“每对数的差的平方”之和最大，这个最大值就称为集合 SSS 的“校验值”。 现在给定一个长度为 nnn 的数列 PPP 以及一个整数 kkk。我们要把数列 PPP 分成若干段，使得每一段的“校验值”都不超过 kkk。求最少需要分成几段。 Advanced CPU Manufacturer (ACM) is one of the best CPU manufacturer in the world. Every day, they manufacture n CPU chips and sell them all over the world. As you may know, each batch of CPU chips must pass a quality test by the QC department before they can be sold. The testing procedure is as follows: 1) Randomly pick m pairs of CPU chips from the batch of chips (If there are less than 2m CPU chips in the batch of chips, pick as many pairs as possible.) 2) For each pair, measure the Relative Performance Difference (RPD) between the two CPU chips. Let DiD_iDi be the RPD of the i-th pair 3) Calculate the Sqared Performance Difference (SPD) of the batch according to the following formula: SPD=∑Di2SPD=∑D_i^2SPD=∑Di2 If there are only 1 CPU in a batch, then the SPD of that batch is 0. 4) The batch of chips pass the test if and only if SPD≤k, where k is a preseted constant Usually they send all the n CPU chips as a single batch to the QC department every day. As one of the best CPU manufacturer in the world, ACM never fail the test. However, with the continuous improvement of CPU performance, they find that they are at risk! Of course they don't want to take any risks. So they make a decision to divide the n chips into several batches to ensure all of them pass the test. What’s more, each batch should be a continuous subsequence of their productions, otherwise the QC department will notice that they are cheating. Quality tests need time and money, so they want to minimize the number of batches. Given the absolute performance of the n chips P1 ... Pn mesured by ACM in order of manufacture, your task is to determine the minimum number of batches to ensure that all chips pass the test. The RPD of two CPU chips equals to the difference of their absolute performance.
想要在职场中立于不败之地？那就来试试全网最全C++题库，让您在练习中快速提升技能。
