名片网页设计代码,手机网站优化排名怎么做,深圳装饰公司,郑州市二七区建设局 网站【原题链接】 【题意说明】 有一组共有N个正整数#xff0c;每次只能取其中的一个数#xff0c;每次没有被取到的数会减少相应的值#xff0c;把每次取到数的值累加#xff0c;问共要取K个数#xff0c;在所有取法中#xff0c;和最大是多少#xff1f; 【问题分析】 快…【原题链接】 【题意说明】 有一组共有N个正整数每次只能取其中的一个数每次没有被取到的数会减少相应的值把每次取到数的值累加问共要取K个数在所有取法中和最大是多少 【问题分析】 快排部分和 首先假定kn我们该如何安排假定每个位置的两个数为xiyi显然sum(xi)这部分的和是固定的那对于yi该怎么安排呢一种安排是把yi从大到小排好序越大的yi越先使用这样就得一个和为sum((i-1)*yi)记为sum0。这部分和是不是所有方案最小的呢我们来讨论一下 假定有另一种方案它是上面排序方案的一种变形其它位置不变只把yi与yj交换其中ij且yiyj)用这个方案的和记为sum1则 sum1-sum0(i-1)*yj(j-1)*yi-(i-1)*yi-(j-1)*yii*yj-i*yij*yi-j*yj(j-i)*(yi-yj)0 同样的方案可以处理其它种方案都的和都比sum0要大所以得按sum0这种方案排序得sum0的值最小即得sum(xi)-sum0的值最大。 这样我们在kn时只要把所有的数据按yi的值先排序即可得到所需要的结果。 那现在对kn呢是不是也可以利用上面的这种想法呢结果是显然的 假定我们从n个数中先取了k个数这k个数该怎么排呢显然这也就是从k个数中选取k个数同上面的想法一样只需要把yi从大到排序就好了。 若照此方法就变成了从n个数中选k个再排序那时间复杂度也太大了吧 更优的方法是先把数据按yi从大到小排序当yi相同时按xi从大到小排序这样选择出来的k个数也必然是有序的。 按照从n个人中去掉一个剩下的n-1个人和最大再从这n-1个人中去掉一个剩下的n-2个人和最大……一直到只剩下k个人即可这其中的计算就需要使用部分和的方法了 转载于:https://www.cnblogs.com/ahmasoi/archive/2012/11/02/2751648.html
