3181. 执行操作可获得的最大总奖励 II
已解答
困难
相关标签
相关企业
提示
给你一个整数数组 rewardValues
,长度为 n
,代表奖励的值。
最初,你的总奖励 x
为 0,所有下标都是 未标记 的。你可以执行以下操作 任意次 :
- 从区间
[0, n - 1]
中选择一个 未标记 的下标i
。 - 如果
rewardValues[i]
大于 你当前的总奖励x
,则将rewardValues[i]
加到x
上(即x = x + rewardValues[i]
),并 标记 下标i
。
以整数形式返回执行最优操作能够获得的 最大 总奖励。
思路:
对于同类型的获取最大总奖励I,由于数据量小,因此采用01背包问题的思路,在O(N^2)的时间复杂度内也能顺利通过,本题由于数据长度和数据大小都是5*1e4,因此最坏时间复杂度是2.5*1e9,超出了时间上限。此处考虑时间的优化。
本题一层循环是遍历整个数组,是无法优化的,那么优化就是内层循环。内层循环所要进行的操作是将数据在小于reward[i]的总数和都加上reward[i]。由于变化是连续的一部分一起变换,且变换的具体情况和原本另一块区域是一致的,即用(0-----reward[i]-1)去更新(reward[i]-----2*reward[i]-1),且一一对应,因此可以考虑位运算直接左移reward[i]位在进行或运算。这样内部时间复杂度就是O(1)了。
代码处f1是用于保存本次reward[i]可能会影响的区域,之所以j是一个始终向前的指针,是因为在j已经遍历过的区域是一定已经更改成功的区域,即不需要重复更改。然后,之所以还需要一个f1来对f0进行修改,是因为原本f0中只是需要修改一部分的值,如果用f0自己对自己进行修改,那么会出现修改某些不应该被修改的地方。
class Solution {
public:
int maxTotalReward(vector<int>& rewardValues) {
map<int,int>dash;
int n=rewardValues.size();
sort(rewardValues.begin(),rewardValues.end());
if(n>=2&&rewardValues[n-1]==rewardValues[n-2]+1)
return 2*rewardValues[n-1]-1;
bitset<100010>f0,f1;
f0[0]=1;
for(int i=0,j=0;i<rewardValues.size();i++)
{
while(j<rewardValues[i])
f1[j]=f0[j],j++;
f0|=f1<<rewardValues[i];
}
int ans=0;
for(int i=0;i<f1.size();i++)
if(f0[i])ans=i;
return ans;
}
};