做网站可以设账户吗,电子商务平台有什么,公司网站修改怎么做,修改wordpress登录页面尽梨了problemsolutioncodeproblem
丰之崎学园附近共有 nnn 个商店#xff0c;在时刻 000 时#xff0c;英梨梨从学园出发开始购物。
从学园走到任意一个商店#xff0c;或从一个商店走到另一个商店需要 111 单位时间。
如果英梨梨在时刻 ttt 到达了商店 iii #xff0c…
尽梨了problemsolutioncodeproblem
丰之崎学园附近共有 nnn 个商店在时刻 000 时英梨梨从学园出发开始购物。
从学园走到任意一个商店或从一个商店走到另一个商店需要 111 单位时间。
如果英梨梨在时刻 ttt 到达了商店 iii 她需要先花费 ai×tbia_i × t b_iai×tbi 的时间排队 然后才能购买这家商店的物品。
英梨梨想知道在时刻 T0.5T 0.5T0.5 之前她最多能在多少个不同商店买到物品呢
这里假定只会在走路和排队上消耗时间购买物品不消耗时间。
n≤2e5,T≤1e9n\le 2e5,T\le 1e9n≤2e5,T≤1e9。
solution
假设在 ttt 时刻选择 iii 商店购买然后立即到 jjj 商店购买则 jjj 商店会多付出 (ai⋅tbi1)⋅aj(a_i·tb_i1)·a_j(ai⋅tbi1)⋅aj 的时间。
假设在 ttt 时刻选择 jjj 商店购买然后立即到 iii 商店购买则 iii 商店会多付出 (aj⋅tbj1)⋅ai(a_j·tb_j1)·a_i(aj⋅tbj1)⋅ai 的时间。
若选择先 iii 后 jjj 的顺序则需满足 (ai⋅tbi1)⋅aj(aj⋅tbj1)⋅ai⇒(bi1)⋅aj(bj1)⋅ai(a_i·tb_i1)·a_j(a_j·tb_j1)·a_i\Rightarrow (b_i1)·a_j(b_j1)·a_i(ai⋅tbi1)⋅aj(aj⋅tbj1)⋅ai⇒(bi1)⋅aj(bj1)⋅ai。
发现商店的先后顺序与时间 ttt 无关。
所以可以按照这个关系进行商店排序。
最后实际去的商店顺序按照时间排序肯定是按这个关系排序后形成的新序列的一个子序列。
暴力地设 dpi,j:dp_{i,j}:dpi,j: 在遍历到 iii 商店已经排序过在 jjj 个商店买到物品的最少花费时间转移考虑是否进入 iii 商店即可时间复杂度 O(n2)O(n^2)O(n2)。
考虑特殊数据点 ∀iai0\forall_i\ a_i0∀i ai0。
通过时间转移公式可以发现如果 ai≠0a_i\neq 0ai0那么进入商店后的时间是指数级增长的。
这就意味着转移的第二位只需要开到 logT\log TlogT 级别就可以了。
实际上这已经几乎是正解了。
将所有 ai0a_i0ai0 的商店排到最后只考虑 ai≠0a_i\neq 0ai0 的商店按照上面优化后的 dpdpdp 做即可。
最后考虑剩余的时间 T−dpk,iT-dp_{k,i}T−dpk,i 后面能接多少个 ai0a_i0ai0 的商店贪心的将这些特殊商店按照 bbb 升序排序。
时间复杂度O(nlognnlogT)O(n\log nn\log T)O(nlognnlogT)。
code
#include cmath
#include cstdio
#include iostream
#include algorithm
using namespace std;
#define int long long
#define maxn 200005
struct node { int a, b; }it[maxn];
int n, m, T, k;
int dp[maxn][35];void read( int x ) {x 0; char s getchar();while( s 0 or s 9 ) s getchar();while( 0 s and s 9 ) x ( x 1 ) ( x 3 ) ( s ^ 48 ), s getchar();
}signed main() {freopen( eriri.in, r, stdin );freopen( eriri.out, w, stdout );read( n ), read( T );m log( T ) / log( 2 );for( int i 1;i n;i ) read( it[i].a ), read( it[i].b );sort( it 1, it n 1, []( node x, node y ) { return ( x.b 1 ) * y.a ( y.b 1 ) * x.a; } );while( it[k 1].a ) k ;for( int i 0;i n;i )for( int j 1;j m;j ) dp[i][j] T 1;for( int i 1;i k;i )for( int j 1;j m;j )dp[i][j] min( min( T 1, dp[i - 1][j] ), dp[i - 1][j - 1] 1 ( dp[i - 1][j - 1] 1 ) * it[i].a it[i].b );sort( it k 1, it n 1, []( node x, node y ) { return x.b y.b; } );int ans 0;for( int i 0;i m and dp[k][i] T;i ) {int sum T - dp[k][i], cnt 0;for( int j k 1;j n and sum it[j].b;j )cnt , sum - it[j].b 1;ans max( ans, i cnt );}printf( %lld\n, ans );return 0;
}
