D - Manga Market 思维加01背包

Social Infrastructure Information Systems Division, Hitachi Programming Contest 2020

并且， 其中的a如果不等于0 ， 那么肯定a >= 1 , 如果在t 时间访问完ai
那么下一个访问完花费时间是
( t + 1 ) * aj + bj + t , 这就相当于两倍的t还多 ， 照这样加些去， 会变成4t , 8t ,几何式增长， 所以只要30次就够了，
然后考虑到还有a=0的， 所以呢， 如果访问了i个a >= 1 的， 再找到符合T时间a=0超时就行了，二分查找，两者相加<=t , 并且两者相加求最大

#include <bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef pair<ll , ll> Pair ;
const int N = 2e5 + 10 ;
Pair a[N] ;
#define f first
#define s second
ll c[N] , dp[44] ;
bool cmp(Pair a , Pair b)
{
  return a.f * (b.s + 1) >  b.f * (a.s + 1) ;
}
int main()
{
  ll n , t ;
  scanf("%lld%lld" , &n , &t) ;
  int cnt1 = 0 , cnt2 = 0 ;
  for(int i =1 ; i <= n ;i ++)
   {
     ll x , y ;
     scanf("%lld%lld" , &x , &y) ;
     if(x == 0) c[++ cnt1] = y + 1 ;
     else a[++ cnt2] = {x , y} ;
   }
   sort(a + 1 , a + cnt2 + 1 , cmp) ;
   sort(c + 1 , c + cnt1 + 1) ;
   for(int i = 0 ;i <= 30 ;i ++) dp[i] = t + 1 ;
   dp[0] = 0 ;
   for(int i = 1; i <= cnt2 ;i ++)
    for(int j = 30 ;j > 0 ;j --)
     dp[j] = min(dp[j] , (dp[j - 1] + 1) * (a[i].f + 1) + a[i].s) ;
  int ans = 0;
  for(int i = 1; i <= cnt1 ; i ++) c[i] += c[i - 1] ;
  for(int i = 0 ;i <= 30 ;i ++)
   {
     if(dp[i] > t) continue ;
     int j = 0 ;
     if(cnt1)
      j = upper_bound(c + 1 , c + cnt1 + 1 , t - dp[i]) - c - 1 ;
    ans= max(ans , j + i) ;

   }
   cout << ans << endl ;
  return 0 ;
}