[关闭]
@ysner 2018-07-18T23:51:25.000000Z 字数 1168 阅读 2380

[HEOI2015]定价

贪心


题面

你如此计算一个正整数的荒谬程度:

询问在范围内荒谬度最低的数。()

解析

一开始想的是,初始,从低位往高位处理,先看该位能否加到(同时前一位加);再看能否加到
但这样疏漏很多,而且不好针对性,如优先级高。

思路妙多了,从开始,每次最后一个非零数位加一并统计答案,这样完全没有漏情况可能。
复杂度上限???

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #define re register
  8. #define il inline
  9. #define ll long long
  10. #define max(a,b) ((a)>(b)?(a):(b))
  11. #define min(a,b) ((a)<(b)?(a):(b))
  12. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  13. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  14. using namespace std;
  15. int ans=0,mn,now;
  16. il ll gi()
  17. {
  18. re ll x=0,t=1;
  19. re char ch=getchar();
  20. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  21. if(ch=='-') t=-1,ch=getchar();
  22. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  23. return x*t;
  24. }
  25. il int add(re int x)
  26. {
  27. re int res=1;
  28. while(x%10==0) x/=10,res*=10;
  29. return res;
  30. }
  31. il int calc(re int x)
  32. {
  33. while(x%10==0) x/=10;
  34. re int tot=0,las=x%10;
  35. while(x) x/=10,tot++;
  36. return 2*tot-(las==5);
  37. }
  38. int main()
  39. {
  40. re int T=gi();
  41. while(T--)
  42. {
  43. re int l=gi(),r=gi();
  44. mn=calc(l),now=ans=l;
  45. while(1)
  46. {
  47. now+=add(now);
  48. if(now>r) break;
  49. re int t=calc(now);
  50. if(t<mn) mn=t,ans=now;
  51. }
  52. printf("%d\n",ans);
  53. }
  54. return 0;
  55. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注