首页 > 代码库 > 我不管，这就是水题《1》

我不管，这就是水题《1》

2024-10-03 11:49:02   222人阅读

每个人都想要更多的财富，谁都不例外。

输入两个整数n，m，往后是n个整数a[i]，表示每个点上的财富为a[i]

m表示可以进行m次交换，每两个数交换位置，财富也随之变化

最多进行m次交换，问连续最大的财富为多少

输入：

一个整数T，表示T组实例 （T<100）

每组实例有n，和m (0<n<200)(m<1e9);

然后n个整数

输出：

最多交换m次的最大连续和  占一行

 

样例 输入

2 

10 2

2 -10 2 2 2 2 2 2 -10 2

10 0

2 -10 2 2 2 2 2 2 -10 2

样例输出

16

12

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<vector>
#include<math.h>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
#define N 10006
int a[N],q[N],qq[N];
int main()
{
    int T,n,m;
    scanf("%d",&T);
    while(T--)
    {
        int summ=-INF;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        if(m>=n/2) m=n/2;
        for(int i=1;i<=n;i++)
        {
            for(int j=i;j<=n;j++)
            {
                int sum=0;
                int e=0,f=0;
                for(int k=i;k<=j;k++)
                {
                    q[++e]=a[k];
                    sum+=a[k];
                }
                summ=max(summ,sum);
                for(int k=1;k<i;k++)
                    qq[++f]=a[k];
                for(int k=j+1;k<=n;k++)
                    qq[++f]=a[k];
                int w=min(f,min(e,m));
                sort(q+1,q+1+e);
                sort(qq+1,qq+1+f);
                for(int k=1;k<=w;k++)
                {
                    sum-=q[k];
                    sum+=qq[f-k+1];
                    summ=max(summ,sum);
                }

            }
        }
        printf("%d\n",summ);
    }
    return 0;
}

 

我不管，这就是水题《1》


联系
我们