[关闭]
@zzzc18 2017-11-10T03:23:44.000000Z 字数 345 阅读 497

NOIP2017赛前集训3 A.连锁店

TEST


题目

在此输入正文


Solution:

考虑到每个店都可以兑换无限多次,我们可以采用贪心;
首先,如果某个 满足 那一定可以得到无限多个纪念章
对于当前的 我们去找所有满足 ,并从中找一个最小的的值,这样只要还能满足 从里面一直取
具体怎么操作,可以按 排序 ST表(似乎怪怪的)线段树、或者直接按为第一关键字,为第二关键字从小到大排序。
至于计算能得到几个可以:

  1. int cnt=(S-num[loc].a)/val;//val为最小的ai-bi
  2. S=(S-num[loc].a)%val+num[loc].a;
  3. S-=val;cnt++;

不然会 TLE

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注