一天，欧姆诺诺姆来到了朋友家里，他发现了许多糖果。有蓝色和红色两种。他知道每颗红色糖果重Wr克，每颗蓝色糖果重Wb克。吃一颗蓝色糖果会给他带来Hb的欢乐值，吃一颗红色糖果会给他带来Hr的欢乐值。

欧姆诺姆最多只能吃C克的糖果，而且每一颗糖果不能只吃一半。现在他想通过吃蓝色和红色的糖果来获得最大的欢乐值。

样例解释：每一种糖果吃两颗即可。

单组测试数据。输入占一行有四个整数C,Hr,Hb,Wr,Wb (1≤C,Hr,Hb,Wr,Wb≤10^9).

输出最大可能获得的欢乐值。

样例输入110 3 5 2 3

样例输出116

基本方法：

一、枚举r糖果和b糖果

二、枚举一个就可以确定另一个，所以枚举r糖果或b糖果
显然这两种都会超时

数据范围<=10^9，显然要用 根号或log级别的算法
假设wr<wb
若wb>=根号c，那么wb 最多只能取 根号c 个
这就把 wb>根号c 的枚举优化到了 根号 级
若wb<根号c
  假设 hr/wr < hb/wb
  可化为 hr*wb < wr*hb
  不妨设 r糖果wb个，那么占据 wb*wr 的空间，得到 wb*hr
  那么在wb*wr的空间里，就可以放 wr个b糖果，得到 wr*hb
  因为 hr*wb < wr*hb 
  所以 若r糖果吃 wb个，那么b糖果吃 wr个更优

所以 r糖果 吃的个数不超过 wb个，可以枚举 r糖果
因为 没吃wb个r糖果，都可以转为 吃 wr个b糖果替代

这样我们就优化到了根号n

这种优化并没有涉及其他的算法，
在原来枚举方法的基础上，找制约关系减少枚举

枚举 r和b 到 枚举 r或b ，
因为r和b两者 占据的总空间固定
再到根号n枚举，
因为 通过 两者 自带的属性找到了制约关系

#include<iostream>#include<cmath>#include<algorithm>#define ll long longusing namespace std;ll c,hr,hb,wr,wb,ans;int main(){    cin>>c>>hr>>hb>>wr>>wb;    if(wr>wb)     {        swap(wr,wb);        swap(hr,hb);    }    if(wb>=sqrt(c))     {        for(int i=0;i*wb<=c;i++)        ans=max(ans,i*hb+(c-wb*i)/wr*hr);    }    else    {        if(1.0*hr/wr>1.0*hb/wb)        {            swap(wr,wb);            swap(hr,hb);        }        for(int i=0;i<wb;i++)        {            if(i*wr>c) break;            ans=max(ans,i*hr+(c-i*wr)/wb*hb);        }          }    cout<<ans;}

注意在枚举r糖果时，不能超过总容量