09:LGTB 学分块
2018-06-17 22:12:56来源:未知 阅读 ()
- 总时间限制:
- 10000ms
- 单个测试点时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
-
LGTB 最近在学分块,但是他太菜了,分的块数量太多他就混乱了,所以只能分成 3 块
今天他得到了一个数组,他突然也想把它分块,他想知道,把这个数组分成 3 块,块可以为空。假设 3 块各自的和中的最大值最小
请输出分完之后 3 块中的最大值
- 输入
- 输入第一行包含一个整数 n 代表数组大小
接下来 n 个整数 a1 , a2 , ..., a n ,代表数组 - 输出
- 输出包含 1 个整数,代表分块完成后 3 块中的最大值
- 样例输入
-
10 2 5 1 4 7 3 6 2 5 1
- 样例输出
-
14
- 提示
- 对于 40% 的数据,1 ≤ n ≤ 10
对于 70% 的数据,1 ≤ n ≤ 1e3
对于 100% 的数据,1 ≤ n ≤ 1e5 , 1 ≤ ai ≤ 1e7
- 查看
- 提交
- 统计
- 提问
- 全局题号
- 7414
- 提交次数
- 14
- 尝试人数
- 7
- 通过人数
- 2
你的提交记录
# | 结果 | 时间 |
4 | Accepted | 07-16 |
3 | Wrong Answer | 07-16 |
2 | Time Limit Exceeded | 07-16 |
1 | Time Limit Exceeded | 07-16 |
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #define lli long long int 6 using namespace std; 7 const lli MAXN=100000001; 8 void read(lli &n) 9 { 10 char c='+';lli x=0;bool flag=0; 11 while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;} 12 while(c>='0'&&c<='9') 13 x=(x<<1)+(x<<3)+c-48,c=getchar(); 14 flag==1?n=-x:n=x; 15 } 16 lli a[MAXN]; 17 lli l,r; 18 lli n; 19 bool pd(lli num) 20 { 21 lli now=0; 22 lli tot=0; 23 for(lli i=1;i<=n;i++) 24 { 25 if(now+a[i]<num) 26 now+=a[i]; 27 else if(now+a[i]==num) 28 tot++,now=0; 29 else if(now+a[i]>num) 30 tot++,now=a[i]; 31 } 32 if(now) 33 tot++; 34 if(tot>3) 35 return 0; 36 else 37 return 1; 38 } 39 int main() 40 { 41 read(n); 42 for(lli i=1;i<=n;i++) 43 read(a[i]),r+=a[i],l=max(l,a[i]); 44 while(l<=r) 45 { 46 lli mid=(l+r)>>1; 47 if(pd(mid)) 48 r=mid-1; 49 else 50 l=mid+1; 51 } 52 printf("%lld",l); 53 return 0; 54 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 测量C++程序运行时间 2020-04-17
- Emergency Evacuation(最短下车时间)———(思维) 2020-04-11
- linux环境下的时间编程 2020-03-27
- C++常见编程--获取当前系统时间 2020-02-25
- c++-字符串和时间操作 2019-12-24
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash