手机网站地址,赣州北京网站建设,网站如何进行seo,建设公司大还是建筑公司大目录
题目#xff1a;
示例#xff1a;
分析#xff1a;
代码#xff1a; 题目#xff1a; 示例#xff1a; 分析#xff1a;
给我们一个数组表示每个菜的满意度#xff0c;我们可以指定做哪些菜以及做的顺序#xff0c;需要我们凑到一个系数的最大值#xff0c…目录
题目
示例
分析
代码 题目 示例 分析
给我们一个数组表示每个菜的满意度我们可以指定做哪些菜以及做的顺序需要我们凑到一个系数的最大值系数的公式为 菜的满意度 * 轮到做完这盘菜所耗的时间包括等待时间。
我们可以知道决定这个系数大小的有两个因素第一个是满意度另一个其实是做菜的顺序越是后面做的菜第二个因素就越大系数也就越大。
所以我们定下主基调了满意度越大的菜我们就放到越后面去做因此我们可以先对满意度进行排序。做菜的顺序我们就定下来了剩下的问题就是选择做哪些菜。
比较直观的选择就是我们只选择满意度为正数的菜因为如果选择了负数那么会导致总体的满意度减少。
但是事实是有时候我们选择满意度为负数的菜反而会让总体的满意度上升因为如果我们先做了负数的菜后面再做满意度高的菜则会使得等待时间变久这样子满意度系数也会更大。
如果满意度为正我们就必须选择要做这盘菜重点在于我们应该如何挑选满意度为负数的菜。
一盘菜能贡献的满意度系数为满意度乘上等待时间那么是不是就说明在一盘菜之前每多做一盘菜那么这盘菜的满意度系数就会多加上这盘菜的满意度转换成数学式子就是 i * ( j 1 ) i * j i 。
我们逆向思考一下我们一开始说满意度越高的菜我们越后面做这个是没问题的但是不利于我们做这道题我们可以先假设我做满意度最高的菜如果后面的菜我需要做了我再反悔一下我改成后面的菜变成第一个做的菜而一开始先做的满意度最高的菜我改成第二个做的这时我只需要将系数总和再加上满意度最高的菜的满意度就可以完成反悔的操作。 也就是说我之后每做一盘菜那么我们的系数之和就会加上之前已经做过的菜的满意度之和了这也就是前缀和。
因此如果遇到了满意度为负数的菜只要这个菜的满意度加上前缀和大于0了那么总的满意度系数还是会增加的我们就可以去做这盘菜。
这样做菜的顺序和做菜的选择我们都搞定了这道题也就迎刃而解了。
代码
class Solution {
public:int maxSatisfaction(vectorint satisfaction) {int res0;//前缀和int cache0;int nsatisfaction.size();//从大到小排序sort(satisfaction.begin(),satisfaction.end(),[](auto a,auto b){return ab;});for(int i0;in;i){//如果是正数,则肯定是正收益,那么直接加上//如果是负数,如果扣掉前缀和之后仍有盈余,那么也加上if(satisfaction[i]0||-1*satisfaction[i]cache){cachesatisfaction[i];rescache;}}return res;}
};
