给定一个长度为 n 的数组 a,你需要将数组划分为若干个互不相交的连续区间,使得每个区间中的元素总和不超过 m,并且数组的每个元素都恰好属于其中一个区间。
定义每个区间的权值为 w,其计算方式如下:令 mex 表示区间中未出现的最小非负整数,则 w=mex4;
现在,你需要找到一种划分数组的方式,使得所有区间的权值之和最大,并输出这个最大权值。
样例:
in:
5 5
1 3 2 0 1
out:
81
我的代码:
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int a[200005];
int b[200005];
int main()
{
int n,m;
cin >> n >> m;
for(int i = 1;i <= n;i++)
{
cin >> a[i];
b[a[i]]++;
}
long long ans = 0;
long long sum = 0;
long long i;
for(i = 0;;)
{
bool flag = 0;
if(b[i] && sum + i <= m)
{
b[i]--;
sum += i;
}
else
{
sum = 0;
ans += i*i*i*i;
i = 0;
flag = 1;
if(b[0] == 0) break;
}
if(!flag) i++;
}
cout << ans << endl;
return 0;
}
思路是贪心,因为如果不连续就是浪费数字,所以模拟求解,但只得20。
