cf1073d Berland Fair

题解：

　　可以发现，每走完一圈付的钱和买的数量是有周期性的，即如果没有因为缺钱而买不起某家店的东西，那么这一圈的所以决策将会和上一圈相同，这个应该是很好理解的，想想就好了。

　　因为钱数固定时，决策固定，所以每次都O(n)扫一遍看当前情况下走一圈会花多少钱。

　　然后直接一直取这么多钱，直到钱不够为止，再进行下一次计算走一圈的钱数，显然用类似取模的东西可以解决。

　　为什么这样的复杂度是正确的呢？

　　一开始觉得是$n^2$的，还想了半天如何优化，但其实因为每次钱数都取了模，而一个数每次取模至少会减少一半，所以其实只会进行log次，所以复杂度是$nlogn$的

 #include<bits/stdc++.h>

 using namespace std;

 #define R register int

 #define AC 230000

 #define LL long long

 int n, top;

 LL ans, t, minn = 10000000000000000LL;

 LL s[AC];

 inline LL read()

 {

     LL x = ;char c = getchar();

     while(c > '' || c < '') c = getchar();

     while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

     return x;

 }

 inline void upmin(LL &a, LL b){

     if(b < a) a = b;

 }    

 void pre()

 {

     n = read(), t = read();

     for(R i = ; i <= n; i ++)

         s[i] = read(), upmin(minn, s[i]);

 }

 void work()

 {

     while(t >= minn)

     {

         LL tmp = t, rnt = ;

         for(R i = ; i <= n; i ++)

             if(tmp >= s[i]) tmp -= s[i], ++ rnt;

         tmp = t - tmp;//获得实际消耗的钱

         LL k = t / tmp;

         ans += k * rnt;

         t -= k * tmp;

     }

     cout << ans << endl;

 }

 int main()

 {

 //    freopen("in.in", "r", stdin);

     pre();

     work();

 //    fclose(stdin);

     return ;

 }

巴特西

cf1073d Berland Fair

最新文章

热门文章