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;
}
};
