@zzzc18
2017-11-10T11:23:44.000000Z
字数 345
阅读 1199
TEST
考虑到每个店都可以兑换无限多次,我们可以采用贪心;
首先,如果某个 满足 那一定可以得到无限多个纪念章
对于当前的 我们去找所有满足 的 ,并从中找一个最小的的值,这样只要还能满足 从里面一直取
具体怎么操作,可以按 排序 ST表(似乎怪怪的)线段树、或者直接按为第一关键字,为第二关键字从小到大排序。
至于计算能得到几个可以:
int cnt=(S-num[loc].a)/val;//val为最小的ai-bi
S=(S-num[loc].a)%val+num[loc].a;
S-=val;cnt++;
不然会 TLE