hdu_5802_Windows 10(贪心)

题目链接：hdu_5802_Windows 10

题意：

给你两个音量a,b，要让你将音量a变到音量b，up:每秒只能一次加1的音量，down:如果连续按x秒，那么就会减2^x-1的音量

题解：

对于a<=b，直接输出a-b就行

对于a>b：

要考虑3种情况：

1. 直接连按x秒

2. 先up到2^x-1,然后再按x秒

3. 先连按x秒，再up到b

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 
 5 ll p[40];
 6 int t,a,b;
 7 void init()
 8 {
 9     ll tp=2;
10     p[0]=1;
11     for(int i=1;i<=32;i++)p[i]=tp+p[i-1],tp*=2;
12 }
13 
14 inline void up(int&a,int b){if(a>b)a=b;}
15 
16 int fuck()
17 {
18     if(b==0)
19     {
20         int pos=lower_bound(p,p+32,a)-p;
21         return pos+1;
22     }
23     int cnt=0,now=0,ans=INT_MAX;
24     while(a!=b)
25     {
26         int cha=a-b,tmp,ti;
27         int pos=lower_bound(p,p+32,cha)-p;
28         tmp=a-p[pos],tmp=tmp<0?0:tmp;
29         ti=b-tmp-cnt,ti=ti<0?0:ti;
30         up(ans,pos+1+now+ti+cnt);//2，3情况合并处理
31         if(p[pos]>cha)pos--;
32         a-=p[pos],now+=pos+1;//第一种情况
33         if(a==b)
34         {
35             up(ans,now+cnt);
36             break;
37         }
38         cnt++;//停顿次数
39     }
40     return ans;
41 }
42 
43 int main()
44 {
45     init();
46     scanf("%d",&t);
47     while(t--)
48     {
49         scanf("%d%d",&a,&b);
50         if(a<=b)printf("%d
",b-a);
51         else printf("%d
",fuck());
52     }
53     return 0;
54 }

View Code