CF1073D Berland Fair 二分+线段树
2024-10-07 03:44:16
考场上切的,挺简单的~
Code:
#include <cstdio>
#include <algorithm>
#define N 200005
#define inf 1000000004
#define ll long long
#define setIO(s) freopen(s".in","r",stdin) , freopen(s".out","w",stdout)
using namespace std;
ll arr[N];
struct Seg
{
#define lson (now<<1)
#define rson (now<<1|1)
struct Node
{
ll sum,minv;
}t[N<<2];
void pushup(int l,int r,int now)
{
t[now].sum=0;
int mid=(l+r)>>1;
if(mid>=l) t[now].sum+=t[lson].sum, t[now].minv=t[lson].minv;
if(r>mid) t[now].sum+=t[rson].sum, t[now].minv=min(t[now].minv, t[rson].minv);
}
void build(int l,int r,int now)
{
if(l==r)
{
t[now].sum=t[now].minv=arr[l];
return;
}
int mid=(l+r)>>1;
if(mid>=l) build(l,mid,lson);
if(r>mid) build(mid+1,r,rson);
pushup(l,r,now);
}
void update(int l,int r,int now,int p,ll v)
{
if(l==r)
{
t[now].sum=v;
t[now].minv=inf;
return;
}
int mid=(l+r)>>1;
if(p<=mid) update(l,mid,lson,p,v);
else update(mid+1,r,rson,p,v);
pushup(l,r,now);
}
ll query(int l,int r,int now,int L,int R)
{
if(l>=L&&r<=R) return t[now].sum;
int mid=(l+r)>>1;
ll re=0;
if(L<=mid) re+=query(l,mid,lson,L,R);
if(R>mid) re+=query(mid+1,r,rson,L,R);
return re;
}
#undef lson
#undef rson
}seg;
int main()
{
// setIO("fairs");
int i,j,n,cnt;
ll k,tot=0;
scanf("%d%lld",&n,&k);
for(i=1;i<=n;++i) scanf("%lld",&arr[i]);
cnt=n;
seg.build(1,n,1);
while(1)
{
int l=1,r=n,mid,ans=0;
while(l<=r)
{
mid=(l+r)>>1;
if(seg.query(1,n,1,1,mid)<=k)
{
ans=mid,l=mid+1;
}
else r=mid-1;
}
if(ans==n)
{
tot+=(k/seg.t[1].sum)*cnt;
k-=(k/seg.t[1].sum)*seg.t[1].sum;
}
else if(seg.t[1].minv>k) break;
else
{
--cnt;
seg.update(1,n,1,ans+1,0);
}
}
printf("%lld\n",tot);
return 0;
}
最新文章
- α-β剪枝算法的java语言实现(非常实用)
- MySql in子句 效率低下优化
- 调用Interop.zkemkeeper.dll无法使用解决方案
- [ZigBee] 16、Zigbee协议栈应用(二)——基于OSAL的无线控制LED闪烁分析(下)
- unity3d Aniso Level 摄像机近地面清楚,远地面模糊
- 无法在web服务器上启动调试。打开的URL的IIS辅助进程当前没有运行。
- xlistview的(java)
- jstl if条件判断字符串代码
- 枚举宏(Adopting Modern Objective-C)
- ViewPager引导
- 利用NSURLSession完成的断点续传功能
- python基础(三)编码,深浅copy
- Newbit 启用淘宝店域名
- Jmeter Smock Test规范设计
- NOIP2018Day1T1 铺设道路
- CSDN去广告插件
- WKWebView使用方法
- centos7安装zabbix server
- 【JVM】查看JVM加载的类及类加载器的方法
- SQL Server进阶 索引