9.18考试 第二题Dinner题解
2024-10-22 05:11:55
当时初步感觉是一个类似动归或者贪心的神题,然而由于本题已经给出顺序,贪心貌似并没有什么道理,所以放弃贪心。然后又由于这是一个环的问题,我想到了“合并石子”那种环转链的思路,然后就是一个O(n^2*m)的近似背包的打法,虽然没有去打,但应该可行吧……
然后我又发现这道题貌似可以二分答案来进行check,然后我们就需要去枚举每一次的起始点,并进行模拟,然后加了一个剪枝即如果当前点的前缀和大于当前check的值,说明我们已经在给第一个点第一份菜单时给了他第二份菜单,而这又是不可行的,否则我们也不会搜到这了。于是乎打了一个最坏O(log sumT*n^2)的暴力模拟,当时傻乎乎的期望60分然后结果才得了20分。
正解是的确是二分答案,只不过在check时用的是倍增,由于二分可以达到同样的效果且省事,我就用了二分去打。其实考试时想到了二分去优化,然而实现的时候打挂了,再加上如果二分复杂度就是O(log sum*n*m*log n)而题目也没有说m的范围,我只能默认m也小于等于50000然后……就放弃了80分……
额,这道题是这次考试翻车的主要原因,出题人连对正解有直接影响的m都没说,也真是醉了……
#include<iostream> #include<cstdlib> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> #include<cmath> #include<map> #include<vector> #define N 50005 using namespace std; int n,t[N],mt,sm,m; ]; int get(int li,int ri,int L) { int t=li; while(li<=ri) { ; ]<=L) li=mid+; ; } ; } bool check(int L) { ;i<=n;i++) { if(sum[i]>L)break; ; ;j++) { j=,L); ) js++; if(js>m)break; } ; } ; } int main() { scanf("%d%d",&n,&m); ;i<=n;i++) { scanf("%d",&t[i]); if(mt<t[i])mt=t[i]; } ;i<=n*;i++) { int to=i; if(i>n)to-=n; sum[i]=t[to]+sum[i-]; } int li=mt,ri=sum[n],ans; while(li<=ri) { ; if(check(mid)) { ans=mid; ri=mid-; } ; } printf("%d\n",ans); ; }
最新文章
- controller共享数据
- 同一服务器配置DataGuard
- centos6.5\win7双系统安装配置
- Android开源中国客户端学习 (自定义View)左右滑动控件ScrollLayout
- Swift - 单例模式的实现
- Delphi使用大图标编译程序
- 使sublimetext3在ubuntu下可以打中文和在windows的dos命令行下正常显示中文
- python3的一些改动常用到的
- TopCoder SRM 566 Div 1 - Problem 1000 FencingPenguins
- x86汇编语言实践(1)
- python:函数和循环判断
- 【Java编程思想笔记】注解--自定义注解
- P1348 Couple number
- Socket编程(网络编程)
- 新页面,简单的tree视图写法
- 【转载】LCT
- 深入理解java虚拟机---虚拟机工具VisualVM(十九)
- 开源项目PullToRefresh详解(一)——PullToRefreshListView
- 用threading和Queue模块实现多线程的端口扫描器
- java继承-重写-super实例补充
热门文章
- 图像滤镜艺术---流行艺术风滤镜特效PS实现
- Win8 Metro(C#)数字图像处理--3.1图像均值计算
- Win10《芒果TV》春季商店版更新v3.3.0:全新视觉蜕变&;支持快男直播
- 微信小程序把玩(二)window配置
- AlwaysOn数据同步暂停及回退技术
- WebApi实现验证授权Token,WebApi生成文档等 - CSDN博客
- Tensorflow初级篇
- Rendering in Delphi using TCanvas (FMX)
- mqtt消息推送
- 创建服务消费者(Ribbon)