二分梳理

文章目錄

• ​​前言​​
• ​​一、二分适用的情況​​
• ​​二、二分的一般流程​​
• ​​三、整數二分​​

• ​​1.需要注意的​​
• ​​2.例題​​

• ​​四、浮點數二分​​

• ​​1.需要注意的地方​​
• ​​例題​​

前言

這周學習了二分，借此篇部落格來複習并梳理二分的内容。

一、二分适用的情況

大多數要用到二分的題一般都有以下特點：

1.資料單調

2.需要在單調的資料中找到某一個符合條件的數

二、二分的一般流程

1.确定二分的對象
2.确定二分的邊界
3.編寫check函數或者說判斷左右區間更新的條件      

三、整數二分

1.需要注意的

出循環的時候，因為是l==r，是以兩者皆可。

2.例題

Polycarpus loves hamburgers very much. He especially adores the hamburgers he makes with his own hands. Polycarpus thinks that there are only three decent ingredients to make hamburgers from: a bread, sausage and cheese. He writes down the recipe of his favorite “Le Hamburger de Polycarpus” as a string of letters ‘B’ (bread), ‘S’ (sausage) и ‘C’ (cheese). The ingredients in the recipe go from bottom to top, for example, recipe “ВSCBS” represents the hamburger where the ingredients go from bottom to top as bread, sausage, cheese, bread and sausage again.

Polycarpus has nb pieces of bread, ns pieces of sausage and nc pieces of cheese in the kitchen. Besides, the shop nearby has all three ingredients, the prices are pb rubles for a piece of bread, ps for a piece of sausage and pc for a piece of cheese.

Polycarpus has r rubles and he is ready to shop on them. What maximum number of hamburgers can he cook? You can assume that Polycarpus cannot break or slice any of the pieces of bread, sausage or cheese. Besides, the shop has an unlimited number of pieces of each ingredient.

Input

The first line of the input contains a non-empty string that describes the recipe of “Le Hamburger de Polycarpus”. The length of the string doesn’t exceed 100, the string contains only letters ‘B’ (uppercase English B), ‘S’ (uppercase English S) and ‘C’ (uppercase English C).

The second line contains three integers nb, ns, nc (1 ≤ nb, ns, nc ≤ 100) — the number of the pieces of bread, sausage and cheese on Polycarpus’ kitchen. The third line contains three integers pb, ps, pc (1 ≤ pb, ps, pc ≤ 100) — the price of one piece of bread, sausage and cheese in the shop. Finally, the fourth line contains integer r (1 ≤ r ≤ 1012) — the number of rubles Polycarpus has.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Output

Print the maximum number of hamburgers Polycarpus can make. If he can’t make any hamburger, print 0.

Examples

Input

BBBSSC

6 4 1

1 2 3

4

Output

2

Input

BBC

1 10 1

1 10 1

21

Output

7

Input

BSC

1 1 1

1 1 3

1000000000000

Output

200000000001

分析：

在這道題中，可以很輕易地想到二分漢堡包的數量，當制作mid個漢堡包所需的錢大于已經有的錢時，便使r=mid。

代碼如下：

#include<bits/stdc++.h>
using namespace std;
int b,s,c;
int pb,ps,pc;
long long mn,ans=0;
int B=0,S=0,C=0;

int main()
{
  string h;
  cin>>h;
  cin>>b>>s>>c;//已經有的數量 
  cin>>pb>>ps>>pc;//每次qian
  cin>>mn;//錢 
  int len=h.size();
  for(int i=0;i<len;i++)
  {
    if(h[i]=='B')
    {
      B++;
    }
    else if(h[i]=='S')
    {
      S++;
    }
    else
    {
      C++;
    }
  }//每個漢堡需要的材料數 
  long long every=B*pb+C*pc+S*ps;//每個漢堡的錢 
  long long l=0,r=1e14;
  long long mid=(r+l)/2;//制作漢堡個數 
  while (l<=r) {
    long long mid = (l+r)/2;
    long long cb=mid*B-b,cs=mid*S-s,cc=mid*C-c;
    if(cb<0)cb=0;
    if(cs<0)cs=0;
    if(cc<0)cc=0;
    long long nm=cb*pb+cs*ps+cc*pc;//需要的錢
    if (nm<=mn)ans=mid;
    if (nm>mn)r=mid-1;
    else l=mid+1;
  }
  printf("%lld\n",ans);
}      

需要注意的點:在計算制作mid個漢堡包剩餘的各個材料時，若其小于0，則要讓其等于0，否則便會啊吧啊吧。

四、浮點數二分

1.需要注意的地方

• 不同于整數二分，在浮點數二分中，若讓r>l為跳出循環的條件，則可能因為循環次數過多而逾時，是以，根據題目要求，一般會讓r-l大于一個很小的數。（例如，題目要求最終結果與答案的偏差小于1e-6，則可以讓r-l>1e-8）

例題

#include<bits/stdc++.h>
using namespace std;
double f(double x)
{
    return 42*pow(x,6)+48*pow(x,5)+21*pow(x,2)+10*x;
}
double F(double x,double y)
{
    return 6*pow(x,7)+8*pow(x,6)+7*pow(x,3)+5*pow(x,2)-y*x;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        double y;
        scanf("%lf",&y);
        double l=0.0,r=100.0;
        double mid;
        while(r-l>1e-9)
        {
            mid=(r+l)/2;
            if(f(mid)>y)
            {
                r=mid;
            }
            else
            {
                l=mid;
            }
        }
        printf("%0.4lf\n",F(mid,y));
    }
    return 0;
}