Codeforces 799 D. Field expansion
2024-08-31 02:19:30
题目链接:http://codeforces.com/contest/799/problem/D
因为${a_i>=2}$那么一个数字至多操作${log_{2}^{max(a,b)/min(h,w)}}$之后就会超过给定的${a,b}$,所以可以搜索,考虑复杂度问题我们就直接随机化,显然按照a_i的大小从大往小选。
辣鸡出题人没有把$h,w$旋转$90$度的情况放在PP里面,我的rating啊...
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<cstring>
using namespace std;
#define maxn 1001000
#define llg long long
#define inf 0x7fffffff
#define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
llg n,m,a[maxn],c,d,w,h,ans=inf,f[maxn]; bool cmp(llg a,llg b) {return a>b;} inline int getint()
{
int w=,q=; char c=getchar();
while((c<'' || c>'') && c!='-') c=getchar(); if(c=='-') q=,c=getchar();
while (c>='' && c<='') w=w*+c-'', c=getchar(); return q ? -w : w;
} void work()
{
llg cs=;
llg x=c,y=d;
while (x<h || y<w)
{
cs++;
if (cs>n) return ;
if (x>=h) {y*=a[cs]; continue;}
if (y>=w) {x*=a[cs]; continue;}
if (rand()%) x*=a[cs];else y*=a[cs];
}
ans=min(ans,cs);
} int main()
{
yyj("D");
cin>>h>>w>>c>>d>>n;
for (llg i=;i<=n;i++) a[i]=getint(),f[a[i]]++;
sort(a+,a+n+,cmp);
// n=min(n,(llg)40);
while ((double)clock()/CLOCKS_PER_SEC<=0.91) work(),swap(h,w),work(),swap(h,w);
if (ans==inf) ans=-;
cout<<ans; return ;
}
最新文章
- 一些kvm虚拟机操作的命令
- JQUERY DIALOG窗格内不能使用FORM
- 【转】SVN的dump文件导入
- 多线程的Python 教程--“贪吃蛇”
- C#常用简单线程实例
- jsconsole
- java反射机制初探
- js实现input输入框只能输入数字的功能
- SQL Server 内存泄露(memory leak)——游标导致的内存问题
- CSS传统布局之页面布局实例
- linux 终端相关
- JS实例——间歇循环滚动
- sublime text 3 3126 注册码+中文包
- 自适应Simpson积分
- 1.Java关键字和保留字
- Spark ML源码分析之四 树
- Maven集成dubbo时报错 Missing artifact com.alibaba:dubbo:jar:2.8.4
- python常见面试题(mark)
- DS二叉树--二叉树之父子结点
- [0day]微软XP系统右键菜单任意DLL却持
热门文章
- spring batch (四) Job的配置及配置文件说明介绍
- stm32高级定时器的应用——spwm
- MailKit使用IMAP读取邮件找不到附件Attachments为空的解决方法
- SqlServer 字段拼接
- ASP.NET gridview导出excel,防止繁体产生有乱码的方式
- [PHP] 编写爬虫获取淘宝网上所有的商品分类以及关键属性 销售属性 非关键属性数据
- 日志入库-log4j-mysql连接中断问题
- datatable的select()结果直接修改,会体现在表上
- flask 异步发送邮件
- Oarcle之单行函数(下)