考场上切的,挺简单的~

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;
}

  

最新文章

  1. α-β剪枝算法的java语言实现(非常实用)
  2. MySql in子句 效率低下优化
  3. 调用Interop.zkemkeeper.dll无法使用解决方案
  4. [ZigBee] 16、Zigbee协议栈应用(二)——基于OSAL的无线控制LED闪烁分析(下)
  5. unity3d Aniso Level 摄像机近地面清楚,远地面模糊
  6. 无法在web服务器上启动调试。打开的URL的IIS辅助进程当前没有运行。
  7. xlistview的(java)
  8. jstl if条件判断字符串代码
  9. 枚举宏(Adopting Modern Objective-C)
  10. ViewPager引导
  11. 利用NSURLSession完成的断点续传功能
  12. python基础(三)编码,深浅copy
  13. Newbit 启用淘宝店域名
  14. Jmeter Smock Test规范设计
  15. NOIP2018Day1T1 铺设道路
  16. CSDN去广告插件
  17. WKWebView使用方法
  18. centos7安装zabbix server
  19. 【JVM】查看JVM加载的类及类加载器的方法
  20. SQL Server进阶 索引

热门文章

  1. python r r+;w w+;a a+;以及加不加b区别
  2. 将多个jar包重新打包成一个jar包
  3. (转载)Nim博弈论
  4. 【Linux-驱动】RTC设备驱动架构
  5. Oracle-DDL 1- 表管理
  6. springmvc的MultipartFile参数如果不上传文件报错的问题
  7. AppCan全局搜索
  8. GoAccess操作手册
  9. AGC009E Eternal Average
  10. 自动化测试报告之allure使用基础指南