Gym 100886J Sockets 二分答案 + 贪心
Description
Statements
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.
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = 2e5+;
int a[maxn],b[maxn];
int num[maxn];
int dp[maxn];
LL sum[maxn];
int n,m;
bool cmp(int a,int b)
{
return a>b;
}
bool check (int val)
{
int begin=,end=val;
LL res = a[]; //能够插多少个
LL can = a[];
int need = ; //有没一定要插一的
int cur = ;
while () {
//res += a[cur];
while (end >= begin && b[end] == need) { //一定要插这个位置
res--; can--; end--;
if (res < ) return false;
}
if (end == begin-) return true;
if (can == ) return false;
// printf ("%d\n",n);
while (can && cur + <= n) { //插尽量多的排插
--can; --res; ++cur;
res += a[cur];
//printf ("%d****\n",a[cur]);
}
if (cur == n) { //所有排插都用完了.
return res >= end-begin+;
}
can = res;
need++;
// printf ("%d\n",res);
}
}
void work ()
{
scanf("%d%d",&n,&m);
for (int i=; i<=n; ++i) scanf("%d",&a[i]);
int lenb=;
for (int j=; j<=m; ++j) {
int x; scanf("%d",&x);
if (x != ) b[++lenb] = x; //0是没用的
}
sort (a+,a++n,cmp);
sort(b+,b++lenb,cmp); int begin=,end=lenb;
while (begin<=end)
{
int mid = (begin+end)/;
if (check(mid))
begin=mid+;
else end=mid-;
}
printf ("%d\n",max(,end));
return ;
}
int main()
{
#ifdef local
freopen("data.txt","r",stdin);
#endif
work();
return ;
}
最新文章
- JS利用取余实现toggle多函数
- ORACLE_UNQNAME
- linux命令:目录结构
- 可维护的javascript
- vi, vim 基本使用(1)
- 在linux上用dd命令实现ghost功能
- MYSQL 体系结构图
- angular-ui-tree
- java内存管理简析
- Python_@修饰器(装饰器)的理解
- 使用mybatis plus 操作数据库
- .Net异步实例讲解
- windows 环境下通过运行快速启动程序
- 使用svn钩子遇到的坑
- win10锁屏或睡眠一段时间后弹不出登录框
- 篮球弹起问题(for循环)
- 学习率设置&;&;训练模型之loss曲线滑动平均
- Python中的对象行为与特殊方法(一)对象的创建与销毁
- mysql学习之路_字段类型与属性
- linux centos系统下升级python版本