NOIP2017赛前集训3 A.连锁店

TEST

题目

Solution:

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

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

不然会 TLE