| Find the max |
| Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB |
| Problem description |
| Yiyiyi4321 is trying to solve the problem 10113 in acm.hnu.cn, and he found that in order to solve this problem he must learn to solve the problem below : Give you a sequence of integers, find K subsequences of the sequence and make their sum Maximized.For example, given a sequence 3, 4, -7, 3, 5, -2, 3, find 2 subsequences from the sequence, you could take 3,4 | 3,5,-2,3, their sum is 16. find 3 subsequences from the sequence, we can take 3,4 | 3,5 | 3 ,whose sum is 18. |
| Input |
| There are two integers, separated by single spaces, in the first line : number of integers n (1 <= n <= 1000), number of subsequences K(0 <= K <= n).The consecutive n lines are the integers. |
| Output |
| Your program should write one integer, the max sum of the K subsequence. |
| Sample Input |
7 2 3 4 -7 3 5 -2 3 |
| Sample Output |
16 |
解题思路：
首先将原数组压缩成正负相间的序列，压缩方法----将连续的整数或者0求和，连续的负数求和，用该和代替这些数。压缩的结果用另一数组保存，压缩过程中记录原数组中正数和0的个数 m， 以及压缩后数组中的正数和0的 个数 n， 还有正数的总和 sum.
有两种情况:
其一： 如果 m < k, 则排序原数组后，依次选取最大负数加于 sum中直到 m==k
其二： 如果 n > k,则从压缩后的数组中（该数组的数是正负或0相间的）选择最大负数max和最小正数 min， 如果| max| > min 则从 sum 中减掉 min, 否则 sum 加上max(max<0)然后压缩 min 或者 max的位置，即将与 max或者min 相邻的三个数求和，直到 n==k,举例如下：
情况一的：
输入：
5 3
1 -2 2 -3 -5
压缩后：1, -2, 2 , -8 count(n)(n>=0) = 2 < 3 于是排序原数数
-5 -3 -2 1 2 得到最大负数 -2 , 所以 sum = sum - 2 = 1
情况二的：
10 3
3 4 -6 2 3 -6 8 -2 6 3
压缩后：7, -6, 5, -6, 8, -2, 9 因为： count(n)(n>=0)=4 > 3
选择最大负数 -2, 最小正数 5 因为 5 > |-2| ，我们压缩 -2 所在位置
压缩后：7,-6,5, -6,15, 此时: count(n)(n>=0)=3==3 结束 ，得到最大和
sum += (-2) , sum = 27
//////////// 代码如下
#include <iostream>
#include <algorithm>
using namespace std;
int a[1002],b[1002];
// 10761
int myMax(int &i, int pri){ // 选择最大负数，返回其绝对值
int j = 0, max;
if(b[0] < 0)
j = 1;
for(max=INT_MIN; j<pri; j++)
if(b[j] < 0 && b[j] > max){
max = b[j];
i = j;
}
return -max;
}
int myMin(int &i, int pri){ // 选择最小正数，返回该数
int j = 0, min;
for(min=INT_MAX; j<pri; j++)
if(b[j] >= 0 && b[j] < min){
min = b[j];
i = j;
}
return min;
}
void myDelete(int i, int& pri){ // 压缩 min,max 所在位置 , 下标为 i
int j=i-1;
b[i+1] = b[i-1] + b[i] + b[i+1];
for(i++; i<pri; j++, i++)
b[j] = b[i];
pri = j;
}
int main(){
int n, m, k, sum, i, j, neg, fneg, fnegn, pri;
cin>>n>>k;
if(k==0){
for(i=0; i<n; i++)
cin>>neg;
cout<<0<<endl;
return 0;
}
for(neg=1, fneg=-1, sum=fnegn=m=pri=i=0; i<n; i++){
cin>>a[i];
if(a[i]>=0){
if(neg < 0){
b[pri++] = neg;
neg = 1;
}
if(fneg == -1)
fneg = 0;
m++;
fneg += a[i];
}else {
if(fneg >= 0){
b[pri++] = fneg;
fnegn++;
sum += fneg;
fneg = -1;
}
if(neg == 1)
neg = 0;
neg += a[i];
}
}
if(fneg > 0){
b[pri++] = fneg;
fnegn++;
sum+=fneg;
}
if(m < k){ // 情况一
sort(&a[0],&a[n]);
for(i=0; i<n ; i++)
if(a[i] >= 0)
break;
for(i--; m<k; m++,i--)
sum+=a[i];
}else{ // 情况二
for(; fnegn>k; fnegn--)
if(myMax(i,pri) > myMin(j,pri)){
sum -= b[j];
myDelete(j,pri);
}else{
sum += b[i];
myDelete(i,pri);
}
}
cout<<sum<<endl;
return 0;
}
评论