首页 > 代码库 > Code Forces Gym 100886J Sockets

Code Forces Gym 100886J Sockets

2024-08-11 21:48:13   220人阅读

J - Sockets

    Time Limit:1000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u

Valera has only one electrical socket in his flat. He also has m devices which require electricity to work. He‘s got n plug multipliers to plug the devices, the i-th plug multiplier has ai sockets.

A device or plug multiplier is supplied with electricity if it is either plugged into the electrical socket, or if it is plugged into some plug multiplier which is supplied with electricity.

For each device j, Valera knows the safety value bj which is the maximum number of plug multipliers on the path between the device and the electrical socket in his flat. For example, if bj = 0, the device should be directly plugged into the socket in his flat.

What is the maximum number of devices Valera could supply with electricity simultaneously? Note that all devices and plug multipliers take one socket to plug, and that he can use each socket to plug either one device or one plug multiplier.

Input

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 2·105), the number of plug multipliers and the number of devices correspondingly.

The second line contains n space-separated integers a1, a2, ..., an (2 ≤ ai ≤ 2·105). Here, the number ai stands for the number of sockets on the i-th plug multiplier.

The third line contains m space-separated integers b1, b2, ..., bm (0 ≤ bj ≤ 2·105). Here, the number bj stands for the safety value of the j-th device.

Output

Print a single integer: the maximum number of devices that could be supplied with electricity simultaneously.

Sample Input

Input

3 5
3 2 2
1 2 2 1 1

Output

4

Input

3 3
2 2 2
1 2 2

Output

3

题意：给你N个插排，a[i]代表第i个插排上面插孔的个数；接着给你M个电器，b[i]代表第i个电器最多能承受的级联层数，然后让你求出最多能有个电器同时工作？
题解：贪心+二分，插排按插孔的个数从大到小排序，电器按所能承受的级联层数从大到小排序，接着在[1,m]的区间内二分答案即可。
            二分的判断主要是看当前区间内(1,mid)的电器能否全部都插在插排上面，如果满足条件，就把当前的mid记录下来。
代码：
技术分享
 1 #include <iostream> 2 #include <queue> 3 #include <stack> 4 #include <cstdio> 5 #include <vector> 6 #include <map> 7 #include <set> 8 #include <bitset> 9 #include <algorithm>10 #include <cmath>11 #include <cstring>12 #include <cstdlib>13 #include <string>14 #include <sstream>15 #define push_back pb16 #define make_pair mp17 #define lson l,m,rt*218 #define rson m+1,r,rt*2+119 #define mt(A) memset(A,0,sizeof(A))20 #define mod 100000000721 using namespace std;22 typedef long long LL;23 const int N=200000+10;24 const LL INF=0x3f3f3f3f3f3f3f3fLL;25 LL a[N],b[N],n,m;26 bool check(LL num)//判断(1.num)内的电器能否全部工作27 {                                //cnt代表的是当前还没有工作的电器的个数28     LL cnt=num,i=1,tot=1,step=0;//step代表级联的层数，初始状态当然为0;29     while(true)                 //tot代表的是当前剩余的插孔的个数30     {31         while(cnt>=1&&b[cnt]<=step)//如果电器的级联层数满足条件，就插上插排32         {33               cnt--;tot--;34         }35         if(cnt<1&&tot>=0)return true;//如果电器插完了，插孔>=0，那说明(1,num)是满足的36         if(tot<0)return false;//插孔<0说明不满足37         LL newtot=0;38         while(tot&&i<=n)//更新插孔的个数39         {40              newtot+=a[i++];41              tot--;42         }43         tot+=newtot;44         step++;//级联层数每次增加一层45     }46 }47 int main()48 {49 #ifdef Local50     freopen("data","r",stdin);51 #endif52     LL i,j,k,l,r,mid,ans;53     cin>>n>>m;54     for(i=1;i<=n;i++)cin>>a[i];55     for(i=1;i<=m;i++)cin>>b[i];56     sort(a+1,a+n+1,greater<LL>());57     sort(b+1,b+m+1,greater<LL>());58     l=1;r=m;59     while(l<=r)60     {61         mid=(l+r)/2;62         if(check(mid))63         {64             ans=mid;//记录答案65             l=mid+1;66         }67         else r=mid-1;68     }69     cout<<ans<<endl;70     return 0;71 }
View Code

 

 

Code Forces Gym 100886J Sockets


联系
我们