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 a_i 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 b_j which is the maximum number of plug multipliers on the path between the device and the electrical socket in his flat. For example, if b_j = 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·10⁵), the number of plug multipliers and the number of devices correspondingly.

The second line contains n space-separated integers a₁, a₂, ..., a_n (2 ≤ a_i ≤ 2·10⁵). Here, the number a_i stands for the number of sockets on the i-th plug multiplier.

The third line contains m space-separated integers b₁, b₂, ..., b_m (0 ≤ b_j ≤ 2·10⁵). Here, the number b_j 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

Input

3 3
2 2 2
1 2 2

Output

3

题意：给你N个插排，a[i]代表第i个插排上面插孔的个数；接着给你M个电器，b[i]代表第i个电器最多能承受的级联层数，然后让你求出最多能有个电器同时工作？
题解：贪心+二分，插排按插孔的个数从大到小排序，电器按所能承受的级联层数从大到小排序，接着在[1,m]的区间内二分答案即可。
            二分的判断主要是看当前区间内(1,mid)的电器能否全部都插在插排上面，如果满足条件，就把当前的mid记录下来。
代码：

 #include <iostream>

 #include <queue>

 #include <stack>

 #include <cstdio>

 #include <vector>

 #include <map>

 #include <set>

 #include <bitset>

 #include <algorithm>

 #include <cmath>

 #include <cstring>

 #include <cstdlib>

 #include <string>

 #include <sstream>

 #define push_back pb

 #define make_pair mp

 #define lson l,m,rt*2

 #define rson m+1,r,rt*2+1

 #define mt(A) memset(A,0,sizeof(A))

 #define mod 1000000007

 using namespace std;

 typedef long long LL;

 const int N=+;

 const LL INF=0x3f3f3f3f3f3f3f3fLL;

 LL a[N],b[N],n,m;

 bool check(LL num)//判断(1.num)内的电器能否全部工作

 {                                //cnt代表的是当前还没有工作的电器的个数

     LL cnt=num,i=,tot=,step=;//step代表级联的层数，初始状态当然为0;

     while(true)                 //tot代表的是当前剩余的插孔的个数

     {

         while(cnt>=&&b[cnt]<=step)//如果电器的级联层数满足条件，就插上插排

         {

               cnt--;tot--;

         }

         if(cnt<&&tot>=)return true;//如果电器插完了，插孔>=0，那说明(1,num)是满足的

         if(tot<)return false;//插孔<0说明不满足

         LL newtot=;

         while(tot&&i<=n)//更新插孔的个数

         {

              newtot+=a[i++];

              tot--;

         }

         tot+=newtot;

         step++;//级联层数每次增加一层

     }

 }

 int main()

 {

 #ifdef Local

     freopen("data","r",stdin);

 #endif

     LL i,j,k,l,r,mid,ans;

     cin>>n>>m;

     for(i=;i<=n;i++)cin>>a[i];

     for(i=;i<=m;i++)cin>>b[i];

     sort(a+,a+n+,greater<LL>());

     sort(b+,b+m+,greater<LL>());

     l=;r=m;

     while(l<=r)

     {

         mid=(l+r)/;

         if(check(mid))

         {

             ans=mid;//记录答案

             l=mid+;

         }

         else r=mid-;

     }

     cout<<ans<<endl;

     return ;

 }

巴特西

Code Forces Gym 100886J Sockets（二分）

J - Sockets

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

Input

Output

Sample Input

Input

Output

Input

Output

最新文章

热门文章