站外题求助
  • 板块题目总版
  • 楼主Ekin123
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/10/9 20:48
  • 上次更新2024/10/9 22:09:42
查看原帖
站外题求助
1235038
Ekin123楼主2024/10/9 20:48

给定一个长度为 nn 的数组 aa,你需要将数组划分为若干个互不相交的连续区间,使得每个区间中的元素总和不超过 mm,并且数组的每个元素都恰好属于其中一个区间。

定义每个区间的权值为 ww,其计算方式如下:令 mexmex 表示区间中未出现的最小非负整数,则 w=mex4w=mex^4

现在,你需要找到一种划分数组的方式,使得所有区间的权值之和最大,并输出这个最大权值。

样例:

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。

image

2024/10/9 20:48
加载中...