例题1.奶牛晒衣服

注意：烘干 \(b\) 是指在每分钟烘干 \(a\) 的基础上额外增加 \(b\) ！！1（太坑人了

二分答案，check 写法显然。

code

#include

using namespace std;

const int N=5e5+5;

int n,h[N],a,b;

int maxn;

bool check(int x)

{

if(b<0)

{

for(int i=1;i<=n;i++) if(a*x

return 1;

}

int sum=0;

for(int i=1;i<=n;i++)

{

if(a*x

}

if(sum<=x) return 1;

else return 0;

}

int main()

{

scanf("%d%d%d",&n,&a,&b);

for(int i=1;i<=n;i++)

{

scanf("%d",&h[i]);

maxn=max(maxn,(h[i]+a-1)/a);

}

//b-=a;

int l=1,r=maxn;

while(l

{

int mid=(l+r)>>1;

if(check(mid)) r=mid;

else l=mid+1;

}

cout<

return 0;

}

例题2.雷达装置

首先将每个点对应可以放置雷达的区间映射到 x 轴上。按照区间右端点排序，贪心把雷达放在右端点。

code

#include

using namespace std;

const int N=1005;

typedef double db;

int n,d;

struct node{

db x,y;

}a[N],b[N];

bool cmp(node x,node y){

return x.y

}

int main()

{

scanf("%d%d",&n,&d);

for(int i=1;i<=n;i++)

{

scanf("%lf%lf",&a[i].x,&a[i].y);

if(fabs(a[i].y)>d) {cout<<"-1"<

db l=sqrt(1.0*(d*d-a[i].y*a[i].y));

b[i].x=a[i].x-l;b[i].y=a[i].x+l;

}

sort(b+1,b+n+1,cmp);

db last=0;int ans=0;

for(int i=1;i<=n;i++)

{

if(i==1) {last=b[i].y;ans++;}

else

{

if(last

}

}

cout<

return 0;

}

例题3.畜栏预定

贪心，每个牛能放就放，不能就新开一个畜栏来放。

用优先队列维护当前畜栏中牛离开时间的最小值。时间复杂度 \(O(n\log n)\)。

code

#include

#define pii pair

#define fi first

#define se second

using namespace std;

const int N=5e4+5;

int n,ans[N],cnt;

struct node{

int l,r,id;

}a[N];

bool cmp(node x,node y){

if(x.l==y.l) return x.r

else return x.l

}

priority_queue,greater > q;

int main()

{

scanf("%d",&n);

for(int i=1;i<=n;i++)

{

scanf("%d%d",&a[i].l,&a[i].r);

a[i].id=i;

}

sort(a+1,a+n+1,cmp);

cnt++;q.push(pii(a[1].r,1));

ans[a[1].id]=1;

for(int i=2;i<=n;i++)

{

if(q.empty())

{

ans[a[i].id]=1;

q.push(pii(a[i].r,1));

continue;

}

if(q.top().fi

{

ans[a[i].id]=q.top().se;

int qwq=q.top().se;

q.pop();q.push(pii(a[i].r,qwq));

}

else

{

cnt++;ans[a[i].id]=cnt;

q.push(pii(a[i].r,cnt));

}

}

cout<

for(int i=1;i<=n;i++) cout<

return 0;

}

例题4.荷马史诗

哈夫曼树板子，虽然这么说，但是本喵以前没学过这东西啊qwq

直接贴个板子代码吧qwq

code

#include

#define int long long

#define pii pair

#define fi first

#define se second

using namespace std;

const int N=1e5+5;

int n,k,w[N],ans;

priority_queue,greater > q;

signed main()

{

scanf("%lld%lld",&n,&k);

for(int i=1;i<=n;i++)

{

scanf("%lld",&w[i]);

q.push(pii(w[i],0));

}

while((q.size()-1)%(k-1)) q.push(pii(0,0));

while(q.size()>1)

{

int sum=0,maxn=0;

for(int i=1;i<=k;i++)

{

if(q.empty()) break;

sum+=q.top().fi;

maxn=max(maxn,q.top().se);

q.pop();

}

ans+=sum;

q.push(pii(sum,maxn+1));

}

cout<

return 0;

}

1.排队接水

根据样例让时间短的人排在前面可以使排队总时间最短。把人按接水时间排序，统计答案。

code

#include

#define int long long

using namespace std;

const int N=1005;

int n,ans,sum;

struct node{

int t,id;

}a[N];

bool cmp(node x,node y){

return x.t

}

signed main()

{

scanf("%lld",&n);

for(int i=1;i<=n;i++) scanf("%lld",&a[i].t),a[i].id=i;

sort(a+1,a+n+1,cmp);

for(int i=1;i<=n;i++) cout<

printf("\n%.2lf\n",1.0*(double)ans/n);

return 0;

}

2.砍树问题

先将树按横坐标排序，则由题意得 \(a_i\le \min(|p_i-p_{i-1}|,|p_{i+1}-p_i|)\)。

据此计算答案，注意判断树可能被全部砍完的情况。

code

#include

using namespace std;

const int N=1e5+5;

const int inf=2e9;

int n,ans;

struct node{

int p,h;

}a[N];

bool cmp(node x,node y){

return x.p

}

int main()

{

scanf("%d",&n);

for(int i=1;i<=n;i++) scanf("%d%d",&a[i].p,&a[i].h);

sort(a+1,a+n+1,cmp);

a[0].p=-inf;a[n+1].p=inf;

for(int i=1;i<=n;i++)

{

int l=a[i].p-a[i-1].p,r=a[i+1].p-a[i].p;

int minn=min(l,r);

ans+=a[i].h-min(minn,a[i].h);

}

cout<

return 0;

}

3.出栈序列

两种情况：

当前栈顶元素大于未入栈元素最大值，将栈顶元素弹出；

反之，将未入栈元素最大值及它以前的元素全部入栈。

可用 \(f\) 数组维护 \([a_i,a_n]\) 的最大值。

code

#include

using namespace std;

const int N=1e6+5;

int n,a[N],maxn[N],tot;

stack q;

int main()

{

scanf("%d",&n);

for(int i=1;i<=n;i++) scanf("%d",&a[i]);

maxn[n]=a[n];

for(int i=n-1;i;i--) maxn[i]=max(a[i],maxn[i+1]);

int qwq=1;

while(a[qwq]!=n) q.push(a[qwq]),qwq++;

q.push(n);qwq++;

while(qwq<=n)

{

tot++;if(tot>10) break;

//cout<

while(!q.empty()&&q.top()>maxn[qwq]) cout<

for(int i=qwq;i<=n;i++)

{

//cout<<"qwq"<

q.push(a[i]);

if(a[i]==maxn[qwq]) {qwq=i+1;break;}

}

}

while(!q.empty()) cout<

return 0;

}

4.序列问题

我们知道，将当前答案再或一个数，结果一定不会变小；将当前答案再与一个数，结果一定不会变大。

所以第一个答案就是所有数或起来，第二个答案连续子序列的长度为 \(k\)。

考虑把每个数二进制拆分，求前缀和来快速算出区间内所有数与起来的答案。

code

#include

using namespace std;

const int N=1e6+5;

int n,k,a[N],ans1,maxn;

int sum[N][35];

bool b[N][35];

int main()

{

scanf("%d%d",&n,&k);

for(int i=1;i<=n;i++) scanf("%d",&a[i]),ans1|=a[i];

cout<

for(int i=1;i<=n;i++)

{

for(int j=0;j<=30;j++) b[i][j]=(a[i]>>j)&1,sum[i][j]=sum[i-1][j]+b[i][j];

}

for(int l=1;l<=n-k+1;l++)

{

int r=l+k-1,ans=0;

for(int j=0;j<=30;j++)

{

int cnt=((sum[r][j]-sum[l-1][j])==k);

//if(j==0) cout<

ans+=(1<

}

//if(ans>0) cout<

maxn=max(maxn,ans);

}

cout<

return 0;

}

5.仙人之环

最优方案是优先选不在环上的边，如果不够就断开最大的环继续选。

dfs 判断环的大小及非环边的数量，然后将环的大小从大到小排序，贪心取边。

代码实现相当恶心，比如笔者忘记了调用 cmp 函数以致调了 1.5h，各位引以为戒（

code

#include

using namespace std;

const int N=4e6+5;

int n,m,k;

struct node{

int nxt,to;

}e[N];

int head[N],cnt;

void add(int u,int v){

e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;

}

bool vis[N];

int tot,h[N],num,ans,dfn[N];

void dfs(int u,int last,int dep)

{

vis[u]=1;dfn[u]=dep;

for(int i=head[u];i;i=e[i].nxt)

{

int v=e[i].to;

if(vis[v]&&v!=last&&dfn[u]>dfn[v]) h[++num]=dfn[u]-dfn[v]+1;

else if(!vis[v]) dfs(v,u,dep+1);

}

}

bool cmp(int x,int y){

return x>y;

}

int main()

{

scanf("%d%d%d",&n,&m,&k);

for(int i=1,u,v;i<=m;i++)

{

scanf("%d%d",&u,&v);

add(u,v);add(v,u);

}

for(int i=1;i<=n;i++) if(!vis[i]) ans++,dfs(i,0,0);

//dfs(1,0);

sort(h+1,h+num+1,cmp);

int ss=0;

for(int i=1;i<=num;i++) ss+=h[i];

int w=m-ss,t=1;

while(k)

{

if(!w)

{

w+=h[t]-1;

t++;k--;

}

else if(k>w) {k-=w,ans+=w,w=0;continue;}

else {ans+=k;break;}

}

cout<

return 0;

}