CodeChef Squirrel and chestnut 题解

骑猪看日落 2021-11-24 01:10 166阅读 0赞

原题链接：[Squirrel and chestnut][]  
题意：有\\(n\\)只松鼠在\\(m\\)棵树下，每一棵树会在\\(t\_i\\)的时间掉下一颗果子，随后每隔\\(p\_i\\)的时间会再落下一颗，现在\\(n\\)只松鼠想要尽可能快地获得\\(k\\)个果实，并且松鼠只能移动一次，求最少时间。  
题解：这一道题，很明显能够想到二分答案，判断也不难，所以我就直接放上代码了：

#include <cstdio> #include <algorithm> using namespace std; #define Maxn 100000 #define ll long long ll a[Maxn+5],b[Maxn+5]; ll c[Maxn+5]; int n,m,k; ll maxm(ll a,ll b){ return a>b?a:b; } bool cmp(ll a,ll b){ return a>b; } bool check(ll mid) { for(int i=0;i<m;i++) { if(mid<a[i]){ c[i]=0; } else{ c[i]=maxm(0,(mid-a[i]+b[i])/b[i]); } } sort(c,c+m,cmp); ll ans=0; for(int i=0;i<min(n,m);i++){ ans+=c[i]; if(ans>=k){ return 1; } } return 0; } int main(){ int t; scanf("%d",&t); ll l,r,mid; while(t--){ scanf("%d%d%d",&m,&n,&k); for(int i=0;i<m;i++){ scanf("%lld",&a[i]); } for(int i=0;i<m;i++){ scanf("%lld",&b[i]); } l=1,r=Maxn-1; while(l<=r){ mid=(l+r)>>1; if(check(mid)){ r=mid; } else{ l=mid+1; } } printf("%lld\n",l); } return 0; }

转载于:https://www.cnblogs.com/withhope/p/11141270.html

[Squirrel and chestnut]: https://www.codechef.com/problems/SQUIRREL

发表评论取消回复

表情：

评论列表（有 0 条评论，166人围观）

还没有评论，来说两句吧...

相关阅读

相关 @codechef - TREEPATH@ Decompose the Tree

目录 @description@ @solution@ @accepted code@ @details@ --------------------

分手后的思念是犯贱/ 2023年06月01日 13:57/ 0 赞/ 7 阅读

相关 @codechef - SONATR@ Sonya and Tree

目录 @description@ @solution@ @accepted code@ @details@ --------------------

分手后的思念是犯贱/ 2023年06月01日 13:56/ 0 赞/ 8 阅读

相关 @codechef - MXMN@ Maximum and Minimum

目录 @description@ @solution@ @accepted code@ @details@ --------------------

男娘i/ 2023年06月01日 13:56/ 0 赞/ 9 阅读

相关 SSY and JLBD 题解

include<iostream> include<cstdio> using namespace std; char a[25][25];

左手的ㄟ右手/ 2023年01月16日 11:15/ 0 赞/ 86 阅读

相关 SQuirreL SQL Client的安装

目录安装 Squirrel 配置 Squirrel 使用 Squirrel 查询数据安装 Squirrel 步骤 1: 下载 Squi

朱雀/ 2022年12月06日 04:03/ 0 赞/ 296 阅读

相关【题解】Bitwise AND of Numbers Range

这道题是leetcode上新出的题目，有兴趣做了一下，轻松通过，具体代码如下所示 class Solution { public: int r

矫情吗；*/ 2022年08月07日 14:56/ 0 赞/ 25 阅读

相关 phoenix_客户端工具Squirrel

1. 客户端工具Squirrel 1) 下载： [https://www.cnblogs.com/laov/p/4137136.html][https_www.cnblog

港控/mmm°/ 2022年05月25日 08:37/ 0 赞/ 174 阅读

相关 [BZOJ4299]Codechef FRBSUM

\[BZOJ4299\]Codechef FRBSUM 题面数集S的ForbiddenSum定义为无法用S的某个子集（可以为空）的和表示的最小的非负整数。例如

ゝ一纸荒年。/ 2021年11月26日 19:34/ 0 赞/ 114 阅读

相关 CodeChef Squirrel and chestnut 题解

原题链接：[Squirrel and chestnut][] 题意：有\\(n\\)只松鼠在\\(m\\)棵树下，每一棵树会在\\(t\_i\\)的时间掉下一颗果子，随后每

骑猪看日落/ 2021年11月24日 01:10/ 0 赞/ 167 阅读

相关 SQuirrel连接hive配置

熟悉了Sqlserver的sqlserver management studio、Oracle的PL/SQL可视化数据库查询分析工具，在刚开始使用hive、phoenix等类s

骑猪看日落/ 2021年05月12日 11:54/ 0 赞/ 460 阅读