Codeforces 1132D Stressful Training 题解

发表于 分类于 ，
本文字数： 14k 阅读时长 ≈ 12 分钟

Codeforces 1132D Stressful Training 题解

题意

有$n$个学生打比赛，第$i$个学生的电脑的初始电量为$a_i$，每分钟使用的电量为$b_i$(即如果在一分钟的开始有$c$格电量，在下一分钟的开始，电量变为$c-b_i$)。整场比赛持续$k$分钟($1\le n\le 2\times10^5,1\le k\le 2\times10^5,1\le a_i\le 10^{12},1\le b_i\le 10^7$)。

在比赛的开始时有一个充电器。你可以选择充电器的输出电量$x$，$x$为一个非负整数，且以后不能更改。在每一分钟的开始，你可以把充电器插在任意一个学生的电脑上(如果一个电脑的用电量为$b_i$，插入了充电器后每分钟会消耗$b_i-x$格电)。每个学生的电脑的电量没有上限。充电器在一个时刻最多给一台电脑充电。

一个学生成功地完成比赛如果在比赛的过程中他的电脑的电量总是一个非负数。比赛结束时电脑的电量无关紧要。

输出充电器最小的输出电量，使得所有的学生都可以成功地完成比赛，或者输出$-1$表示不可能。

题解

考虑二分 充电器的电量。

如果充电器的电量为$x$，$x=y$时可行，则$x=y+1$时一定可行，而$x=y-1$时则不一定。

二分下限为$0$，上限为$2\times10^{12}$就够了(如果您不想算，设为$10^{18}$也可以，欺负log)。

check函数考虑贪心：每次选出当前最快要没电的电脑，给它充一分钟电。

显然，如果一台电脑当前电量为$x$，每分钟消耗的电量为$y$，则给它充电使得它的电量非负的最后时刻为$\left\lfloor\frac{x}{y}\right\rfloor+1$。使用优先队列维护即可。

这样check函数的时间复杂度为$O((n+k)\times\log n)$，总共为$O(\log\text{ans}\times(n+k)\times \log n)$。有点危险：如果优先队列里维护的是pair<long long,pair<long long> >可能会TLE 50，改为结构体擦边AC。

考虑优化：

开$k$个vector，其中第$i$个维护哪些电脑能支撑到的最后时刻为$i$。其它思路同上。

这样check函数的时间复杂度为$O(n+k)$，总共为$O(\log\text{ans}\times(n+k))$。

程序

  • 未优化版本

    • pair<long long,pair<long long> >：image.png
    • struct：image.png
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
      82
      83
      84
      85
      86
      87
      88
      89
      90
      91
      92
      93
      94
      95
      96
      97
      98
      99
      100
      101
      102
      103
      104
      105
      106
      107
      108
      109
      110
      111
      112
      113
      114
      115
      116
      117
      118
      119
      120
      121
      122
      123
      124
      125
      126
      127
      128
      129
      130
      131
      132
      133
      134
      135
      136
      137
      138
      139
      140
      141
      142
      143
      144
      145
      146
      147
      148
      149
      150
      151
      152
      153
      154
      155
      156
      157
      158
      159
      160
      161
      162
      163
      164
      165
      166
      167
      168
      169
      170
      171
      172
      173
      174
      175
      176
      177
      178
      179
      180
      181
      182
      183
      184
      185
      186
      187
      188
      189
      190
      191
      192
      193
      194
      195
      196
      197
      198
      199
      200
      201
      202
      203
      204
      205
      206
      207
      208
      209
      210
      211
      212
      213
      214
      215
      216
      217
      218
      219
      220
      221
      222
      223
      224
      225
      226
      227
      228
      229
      230
      231
      232
      233
      // #pragma GCC optimize(2)
      // #pragma G++ optimize(2)
      // #pragma comment(linker,"/STACK:102400000,102400000")

      // #include <bits/stdc++.h>
      #include <map>
      #include <set>
      #include <list>
      #include <array>
      #include <cfenv>
      #include <cmath>
      #include <ctime>
      #include <deque>
      #include <mutex>
      #include <queue>
      #include <ratio>
      #include <regex>
      #include <stack>
      #include <tuple>
      #include <atomic>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <cfloat>
      #include <chrono>
      #include <cstdio>
      #include <cwchar>
      #include <future>
      #include <limits>
      #include <locale>
      #include <memory>
      #include <random>
      #include <string>
      #include <thread>
      #include <vector>
      #include <cassert>
      #include <climits>
      #include <clocale>
      #include <complex>
      #include <csetjmp>
      #include <csignal>
      #include <cstdarg>
      #include <cstddef>
      #include <cstdint>
      #include <cstdlib>
      #include <cstring>
      #include <ctgmath>
      #include <cwctype>
      #include <fstream>
      #include <iomanip>
      #include <numeric>
      #include <sstream>
      #include <ccomplex>
      #include <cstdbool>
      #include <iostream>
      #include <typeinfo>
      #include <valarray>
      #include <algorithm>
      #include <cinttypes>
      #include <cstdalign>
      #include <stdexcept>
      #include <typeindex>
      #include <functional>
      #include <forward_list>
      #include <system_error>
      #include <unordered_map>
      #include <unordered_set>
      #include <scoped_allocator>
      #include <condition_variable>
      // #include <conio.h>
      // #include <windows.h>
      using namespace std;

      typedef long long LL;
      typedef unsigned int ui;
      typedef unsigned long long ull;
      typedef float fl;
      typedef double ld;
      typedef long double LD;
      typedef pair<int,int> pii;
      #if (WIN32) || (WIN64) || (__WIN32) || (__WIN64) || (_WIN32) || (_WIN64) || (WINDOWS)
      #define lld "%I64d"
      #define llu "%I64u"
      #else
      #define lld "%lld"
      #define llu "%llu"
      #endif
      #define ui(n) ((unsigned int)(n))
      #define LL(n) ((long long)(n))
      #define ull(n) ((unsigned long long)(n))
      #define fl(n) ((float)(n))
      #define ld(n) ((double)(n))
      #define LD(n) ((long double)(n))
      #define char(n) ((char)(n))
      #define Bool(n) ((bool)(n))
      #define fixpoint(n) fixed<<setprecision(n)

      const int INF=1061109567;
      const int NINF=-1044266559;
      const LL LINF=4557430888798830399;
      const ld eps=1e-15;
      #define MOD (1000000007)
      #define PI (3.1415926535897932384626433832795028841971)

      /*
      #define MB_LEN_MAX 5
      #define SHRT_MIN (-32768)
      #define SHRT_MAX 32767
      #define USHRT_MAX 0xffffU
      #define INT_MIN (-2147483647 - 1)
      #define INT_MAX 2147483647
      #define UINT_MAX 0xffffffffU
      #define LONG_MIN (-2147483647L - 1)
      #define LONG_MAX 2147483647L
      #define ULONG_MAX 0xffffffffUL
      #define LLONG_MAX 9223372036854775807ll
      #define LLONG_MIN (-9223372036854775807ll - 1)
      #define ULLONG_MAX 0xffffffffffffffffull
      */

      #define MP make_pair
      #define MT make_tuple
      #define All(a) (a).begin(),(a).end()
      #define pall(a) (a).rbegin(),(a).rend()
      #define Log(x,y) log(x)/log(y)
      #define SZ(a) ((int)(a).size())
      #define rep(i,n) for(int i=0;i<((int)(n));i++)
      #define rep1(i,n) for(int i=1;i<=((int)(n));i++)
      #define repa(i,a,n) for(int i=((int)(a));i<((int)(n));i++)
      #define repa1(i,a,n) for(int i=((int)(a));i<=((int)(n));i++)
      #define repd(i,n) for(int i=((int)(n))-1;i>=0;i--)
      #define repd1(i,n) for(int i=((int)(n));i>=1;i--)
      #define repda(i,n,a) for(int i=((int)(n));i>((int)(a));i--)
      #define repda1(i,n,a) for(int i=((int)(n));i>=((int)(a));i--)
      #define FOR(i,a,n,step) for(int i=((int)(a));i<((int)(n));i+=((int)(step)))
      #define repv(itr,v) for(__typeof((v).begin()) itr=(v).begin();itr!=(v).end();itr++)
      #define repV(i,v) for(auto i:v)
      #define repE(i,v) for(auto &i:v)
      #define MS(x,y) memset(x,y,sizeof(x))
      #define MC(x) MS(x,0)
      #define MINF(x) MS(x,63)
      #define MCP(x,y) memcpy(x,y,sizeof(y))
      #define sqr(x) ((x)*(x))
      #define UN(v) sort(All(v)),v.erase(unique(All(v)),v.end())
      #define filein(x) freopen(x,"r",stdin)
      #define fileout(x) freopen(x,"w",stdout)
      #define fileio(x)\
      	freopen(x".in","r",stdin);\
      	freopen(x".out","w",stdout)
      #define filein2(filename,name) ifstream name(filename,ios::in)
      #define fileout2(filename,name) ofstream name(filename,ios::out)
      #define file(filename,name) fstream name(filename,ios::in|ios::out)
      #define Pause system("pause")
      #define Cls system("cls")
      #define fs first
      #define sc second
      #define PC(x) putchar(x)
      #define GC(x) x=getchar()
      #define Endl PC('\n')
      #define SF scanf
      #define PF printf

      #define j0 J0
      #define j1 J1
      #define jn Jn
      #define y0 Y0
      #define y1 Y1
      #define yn Yn

      inline int Read()
      {
      	int x=0,w=0;char ch=0;while(!isdigit(ch)){w|=ch=='-';ch=getchar();}while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
      	return w?-x:x;
      }
      inline void Write(int x){if(x<0)putchar('-'),x=-x;if(x>9)Write(x/10);putchar(x%10+'0');}

      inline LL powmod(LL a,LL b){LL res=1;a%=MOD;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res%MOD;}
      inline LL gcdll(LL a,LL b){return b?gcdll(b,a%b):a;}
      const int dx[]={0,1,0,-1,1,-1,-1,1};
      const int dy[]={1,0,-1,0,-1,-1,1,1};
      /************************************************************BEGIN************************************************************/
      const int maxn=200010;

      int n,m;
      LL a[maxn],b[maxn];

      struct stu
      {
      	LL x,y,r;

      	inline bool operator <(stu S) const
      	{
      		return r>S.r;
      	}
      };

      inline bool check(LL mid)
      {
      	priority_queue<stu> q;
      	rep1(i,n) q.push({a[i],b[i],a[i]/b[i]});

      	rep1(i,m)
      	{
      		LL x=q.top().x,y=q.top().y,r=q.top().r+1;q.pop();

      		if(r<i) return 0;
      		if(r>=m) return 1;

      		x+=mid;
      		q.push({x,y,x/y});
      	}

      	return 1;
      }

      int main()
      {
      	SF("%d%d",&n,&m);
      	rep1(i,n) SF("%lld",&a[i]);
      	rep1(i,n) SF("%lld",&b[i]);

      	LL l=0,r=1e18; // [l,r)
      	while(l<r)
      	{
      		LL mid=(l+r)/2;
      		if(check(mid)) r=mid; else l=mid+1;
      	}

      	if(check(r)) PF("%lld",r); else PF("-1");

      	return 0;
      }
      /*************************************************************END**************************************************************/

  • 优化版本

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    // #pragma GCC optimize(2)
    // #pragma G++ optimize(2)
    // #pragma comment(linker,"/STACK:102400000,102400000")

    // #include <bits/stdc++.h>
    #include <map>
    #include <set>
    #include <list>
    #include <array>
    #include <cfenv>
    #include <cmath>
    #include <ctime>
    #include <deque>
    #include <mutex>
    #include <queue>
    #include <ratio>
    #include <regex>
    #include <stack>
    #include <tuple>
    #include <atomic>
    #include <bitset>
    #include <cctype>
    #include <cerrno>
    #include <cfloat>
    #include <chrono>
    #include <cstdio>
    #include <cwchar>
    #include <future>
    #include <limits>
    #include <locale>
    #include <memory>
    #include <random>
    #include <string>
    #include <thread>
    #include <vector>
    #include <cassert>
    #include <climits>
    #include <clocale>
    #include <complex>
    #include <csetjmp>
    #include <csignal>
    #include <cstdarg>
    #include <cstddef>
    #include <cstdint>
    #include <cstdlib>
    #include <cstring>
    #include <ctgmath>
    #include <cwctype>
    #include <fstream>
    #include <iomanip>
    #include <numeric>
    #include <sstream>
    #include <ccomplex>
    #include <cstdbool>
    #include <iostream>
    #include <typeinfo>
    #include <valarray>
    #include <algorithm>
    #include <cinttypes>
    #include <cstdalign>
    #include <stdexcept>
    #include <typeindex>
    #include <functional>
    #include <forward_list>
    #include <system_error>
    #include <unordered_map>
    #include <unordered_set>
    #include <scoped_allocator>
    #include <condition_variable>
    // #include <conio.h>
    // #include <windows.h>
    using namespace std;

    typedef long long LL;
    typedef unsigned int ui;
    typedef unsigned long long ull;
    typedef float fl;
    typedef double ld;
    typedef long double LD;
    typedef pair<int,int> pii;
    #if (WIN32) || (WIN64) || (__WIN32) || (__WIN64) || (_WIN32) || (_WIN64) || (WINDOWS)
    #define lld "%I64d"
    #define llu "%I64u"
    #else
    #define lld "%lld"
    #define llu "%llu"
    #endif
    #define ui(n) ((unsigned int)(n))
    #define LL(n) ((long long)(n))
    #define ull(n) ((unsigned long long)(n))
    #define fl(n) ((float)(n))
    #define ld(n) ((double)(n))
    #define LD(n) ((long double)(n))
    #define char(n) ((char)(n))
    #define Bool(n) ((bool)(n))
    #define fixpoint(n) fixed<<setprecision(n)

    const int INF=1061109567;
    const int NINF=-1044266559;
    const LL LINF=4557430888798830399;
    const ld eps=1e-15;
    #define MOD (1000000007)
    #define PI (3.1415926535897932384626433832795028841971)

    /*
    #define MB_LEN_MAX 5
    #define SHRT_MIN (-32768)
    #define SHRT_MAX 32767
    #define USHRT_MAX 0xffffU
    #define INT_MIN (-2147483647 - 1)
    #define INT_MAX 2147483647
    #define UINT_MAX 0xffffffffU
    #define LONG_MIN (-2147483647L - 1)
    #define LONG_MAX 2147483647L
    #define ULONG_MAX 0xffffffffUL
    #define LLONG_MAX 9223372036854775807ll
    #define LLONG_MIN (-9223372036854775807ll - 1)
    #define ULLONG_MAX 0xffffffffffffffffull
    */

    #define MP make_pair
    #define MT make_tuple
    #define All(a) (a).begin(),(a).end()
    #define pall(a) (a).rbegin(),(a).rend()
    #define Log(x,y) log(x)/log(y)
    #define SZ(a) ((int)(a).size())
    #define rep(i,n) for(int i=0;i<((int)(n));i++)
    #define rep1(i,n) for(int i=1;i<=((int)(n));i++)
    #define repa(i,a,n) for(int i=((int)(a));i<((int)(n));i++)
    #define repa1(i,a,n) for(int i=((int)(a));i<=((int)(n));i++)
    #define repd(i,n) for(int i=((int)(n))-1;i>=0;i--)
    #define repd1(i,n) for(int i=((int)(n));i>=1;i--)
    #define repda(i,n,a) for(int i=((int)(n));i>((int)(a));i--)
    #define repda1(i,n,a) for(int i=((int)(n));i>=((int)(a));i--)
    #define FOR(i,a,n,step) for(int i=((int)(a));i<((int)(n));i+=((int)(step)))
    #define repv(itr,v) for(__typeof((v).begin()) itr=(v).begin();itr!=(v).end();itr++)
    #define repV(i,v) for(auto i:v)
    #define repE(i,v) for(auto &i:v)
    #define MS(x,y) memset(x,y,sizeof(x))
    #define MC(x) MS(x,0)
    #define MINF(x) MS(x,63)
    #define MCP(x,y) memcpy(x,y,sizeof(y))
    #define sqr(x) ((x)*(x))
    #define UN(v) sort(All(v)),v.erase(unique(All(v)),v.end())
    #define filein(x) freopen(x,"r",stdin)
    #define fileout(x) freopen(x,"w",stdout)
    #define fileio(x)\
    	freopen(x".in","r",stdin);\
    	freopen(x".out","w",stdout)
    #define filein2(filename,name) ifstream name(filename,ios::in)
    #define fileout2(filename,name) ofstream name(filename,ios::out)
    #define file(filename,name) fstream name(filename,ios::in|ios::out)
    #define Pause system("pause")
    #define Cls system("cls")
    #define fs first
    #define sc second
    #define PC(x) putchar(x)
    #define GC(x) x=getchar()
    #define Endl PC('\n')
    #define SF scanf
    #define PF printf

    #define j0 J0
    #define j1 J1
    #define jn Jn
    #define y0 Y0
    #define y1 Y1
    #define yn Yn

    inline int Read()
    {
    	int x=0,w=0;char ch=0;while(!isdigit(ch)){w|=ch=='-';ch=getchar();}while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    	return w?-x:x;
    }
    inline void Write(int x){if(x<0)putchar('-'),x=-x;if(x>9)Write(x/10);putchar(x%10+'0');}

    inline LL powmod(LL a,LL b){LL res=1;a%=MOD;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res%MOD;}
    inline LL gcdll(LL a,LL b){return b?gcdll(b,a%b):a;}
    const int dx[]={0,1,0,-1,1,-1,-1,1};
    const int dy[]={1,0,-1,0,-1,-1,1,1};
    /************************************************************BEGIN************************************************************/
    const int maxn=200010;

    int n,m;
    LL a[maxn],b[maxn];
    vector<pair<LL,LL> > stu[maxn];

    inline bool check(LL mid)
    {
    	rep(i,m+1) stu[i].clear();
    	rep1(i,n) if(a[i]/b[i]+1<=m) stu[a[i]/b[i]+1].push_back({a[i],b[i]});

    	int k=1;
    	rep1(i,m)
    	{
    		while(stu[k].empty()) k++;

    		if(k<i) return 0;
    		if(k>=m) return 1;

    		LL x=stu[k].back().fs+mid,y=stu[k].back().sc;stu[k].pop_back();
    		if(x/y+1<=m) stu[x/y+1].push_back({x,y});
    	};

    	return 1;
    }

    int main()
    {
    	SF("%d%d",&n,&m);
    	rep1(i,n) SF("%lld",&a[i]);
    	rep1(i,n) SF("%lld",&b[i]);

    	LL l=0,r=1e18; // [l,r)
    	while(l<r)
    	{
    		LL mid=(l+r)/2;
    		if(check(mid)) r=mid; else l=mid+1;
    	}

    	if(check(r)) PF("%lld",r); else PF("-1");

    	return 0;
    }
    /*************************************************************END**************************************************************/
__EOF__