CF732D Exams 二分 贪心

思路:二分+贪心

提交次数:10次以上

错因:刚开始以为二分(边界,$+1or-1$)写错了,调了半天,后来才发现是$ck()$写错了。开始只判了最后是否小于零,而应该中间一旦小于零就$return\space false$

题解:

二分天数(单调性显然)。

$ck(int x)$: 首先$x$天内必须包含所有科目;然后贪心的考每一科的最后一次试(倒着扫一遍);维护一个剩余天数$cnt$,遇到空闲时间或不是最后本科目的一次考试就$++$,否则$-=$本科考试所需的复习天数;一旦$cnt<0$,直接$return\space false$;最后$return\space cnt>=0$。

代码:

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
//你弱,有什么资格休息
#define ull unsigned long long
#define ll long long
#define R register ll
#define pause (for(R i=1;i<=10000000000;++i))
#define In freopen("NOIPAK++.in","r",stdin)
#define Out freopen("out.out","w",stdout)
namespace Fread {
static char B[1<<15],*S=B,*D=B;
#ifndef JACK
#define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)
#endif
inline int g() {
    R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch==‘-‘?-1:fix;
    if(ch==EOF) return EOF; do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;
} inline bool isempty(const char& ch) {return (ch<=36||ch>=127);}
inline void gs(char* s) {
    register char ch; while(isempty(ch=getchar()));
    do *s++=ch; while(!isempty(ch=getchar()));
}
} using Fread::g; using Fread::gs;

namespace Luitaryi {
const int N=1e+5+10;
int n,m,ans=-1,cnt;
int a[N],w[N];
bool vis[N],flg[N];
inline bool ck(int x) { R ret=0,tmp=m;
    memset(vis,0,sizeof(vis)); memset(flg,0,sizeof(flg));
    for(R i=x;i>=1&&tmp;--i) if(a[i]&&!vis[a[i]]) vis[a[i]]=true,flg[i]=true,--tmp;
    if(tmp!=0) return false;
    for(R i=1;i<=x;++i) {
        if(a[i]!=0&&flg[i]) ret-=w[a[i]];
        else ++ret;
        if(ret<0) return false;
    } return ret>=0;
}
inline void main() {
    n=g(),m=g();
    for(R i=1;i<=n;++i) a[i]=g();
    for(R i=1;i<=m;++i) w[i]=g();
    R l=m,r=n+1; while(l<r) {
        R md=l+r>>1;
        if(ck(md)) r=md;
        else l=md+1;
    } printf("%d\n",l==n+1?-1:l);
}
}
signed main() {
    Luitaryi::main();
    return 0;
}


2019.07.14

原文地址:https://www.cnblogs.com/Jackpei/p/11186523.html

时间: 07-15

CF732D Exams 二分 贪心的相关文章

二分+贪心

上海邀请赛热身时候,C题是一个二分+贪心的题目.起初并不会,问了旁边的复旦大神.这几天无意发现VJ上一个专题.擦原来是一个经典类型. 二分+贪心 这类题目注意数据范围,1e8,1e9一般都是这样. 注意事项 二分法有很多写法,推荐用lf+1 < rf的写法.这个也符合计算机中数据存取的原则.对于浮点数,直接就循环100次,精度绝对够. 一般有两种类型,一种是询问最优,即数列中无重复.一种是多个即lower_bound ,upper_bound这类函数问题. 贪心使用,就是这个问题枚举答案可被验证

nyoj586||poj2456 二分+贪心

完全看不懂题意....百度搜搜才看懂题意  然后就参考代码了 和yougth的最大化()nyoj914差不多的方法 二分+贪心 #include <stdio.h> #include <algorithm> using namespace std; int c,a[100005],n; bool judge(int k) { int p=a[0],cnt=1;//也就这里注意点 从1开始 自己想想为啥 for(int i=1;i<n;i++) { if(a[i]-p>=

HDU 4004 The Frog&#39;s Games 二分 贪心

戳这里:HDU 4004 //思路:二分经典入门题...贪心判方案是否可行 1 #include "bits/stdc++.h" 2 using namespace std; 3 int L, n, m; 4 int pos[500010], dis[500010]; 5 6 bool Cant(int Dis_Jump) 7 { 8 int i, Dis_Sum = 0, Count = 0; 9 for(i = 1; i <= n + 1; ++i) { 10 if(dis[

贪心(bnuoj49103+二分+贪心)

贪心 小明喜欢养小鸡,小鸡喜欢吃小米.小明很贪心,希望养s只不同种类的小鸡,小鸡也很贪心,每天除了吃固定的ai粒小米外,还想多吃bi*s粒小米. 小明每天有M(0<=M<=10^9)粒小米可以喂小鸡,小鸡共有N(0<=N<=1000)种.问小明最多可以养多少只小鸡? Input 多组数据,请读到文件尾 第一行,整数N,M,以空格分隔,之后两行,第一行为N个整数ai,第二行为N个整数bi. ai.bi都在int范围内 Output 一行一个整数,s. Sample Input 2 4

poj1505Copying Books 二分+贪心详细总结

前两天花了时间理解了nyoj的586疯牛和nyoj619青蛙过河,满以为自己能重新写出这道题...谁知道..... 题意:有m本书,k个人来抄,每本书有一个书本页数:求使得k个人抄完的最大页数最小,并且每个人都至少要抄一本,然后输出抄书的方案 分析: 这里又涉及到前面nyoj的586疯牛和nyoj619青蛙过河说过的最大值中的最小值,  用前面的例子去理解比较方便 1.我们应该先用二分+贪心算出一个最大页数的最小值--这里和前面的类似 在二分的过程中,我们对于当前考虑的值 x  划分人数的贪心过

【bzoj2097】[Usaco2010 Dec]Exercise 奶牛健美操 二分+贪心

题目描述 Farmer John为了保持奶牛们的健康,让可怜的奶牛们不停在牧场之间 的小路上奔跑.这些奶牛的路径集合可以被表示成一个点集和一些连接 两个顶点的双向路,使得每对点之间恰好有一条简单路径.简单的说来, 这些点的布局就是一棵树,且每条边等长,都为1. 对于给定的一个奶牛路径集合,精明的奶牛们会计算出任意点对路径的最大值, 我们称之为这个路径集合的直径.如果直径太大,奶牛们就会拒绝锻炼. Farmer John把每个点标记为1..V (2 <= V <= 100,000).为了获得更加

POJ - 2456 Aggressive cows(二分+贪心)

题意:把c个牛分进n个摊位,摊位位置已知,所有摊位分布在0 <= xi <= 1,000,000,000,问两头牛间最小距离的最大值. 分析:找所有最小距离取个最大的.所以二分找这个最小的距离,这个最大的最小距离是二分的分界线.贪心来判断当前的最小距离是否能安排下所有的牛. #pragma comment(linker, "/STACK:102400000, 102400000") #include<cstdio> #include<cstring>

Codeforces 589F F. Gourmet and Banquet(二分+贪心)

题目地址:http://codeforces.com/problemset/problem/589/F 思路:先贪心按照右端点值排序(先把对后面影响最小的菜吃掉),二分吃每道菜的时间即可. #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=105; const int maxt=1e5+50

BZOJ_1620_[Usaco2008_Nov]_Time_Management_时间管理_(二分+贪心)

描述 http://www.lydsy.com/JudgeOnline/problem.php?id=1620 N个工作,每个工作其所需时间,及完成的Deadline,问要完成所有工作,最迟要什么时候开始. 分析 我们可以想到二分开始的时间.对于一个给定的时间,判断是否可以完成. 如何判断呢? 我们假设有\(a,b\)两个任务且\(deadline(a)<deadline(b)\). 如果先完成\(b\),那么要求\(time[b]+time[a]<deadline(a)\). 如果先完成\(

LA 4254 Processor 处理器 【二分 贪心 优先队列】

题目链接: http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=21663 二分: 最大值最小的问题通过二分来求解.对处理器速度进行二分之后,问题就转化成了对于给定的处理速度,问处理器是否可以将这些问题处理完. 贪心: 一个贪心的思路就是每个时刻应该尽量 做可以做的任务中,结束时间最早的那个,这样最起码不会使结果更糟.这样就可以枚举每个单位时间,然后去找可以做的并且结束时间最早的那个去做,直到用完这一单位时间或者无任务可做为止.