CF 1490G - Old Floppy Drive 思维，二分

本文主要是介绍CF 1490G - Old Floppy Drive 思维，二分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

https://codeforces.com/problemset/problem/1490/G

题意

给定数组a（如1,2,2,3），构造一个A数组，为a数组的循环拼接（如1,2,2,3,1,2,2,3…）。m个询问，对于每个询问q，输出最小的i，使得A数组前i+1个数字的和大于等于q

思路

我们需要如下几个数组
sum：a的前缀和
max_：a前缀和的最大值

易知max_数组单调不降，可用二分搜索。

在某一次询问q中，如果q<=max_[n]，那就是说答案比n小，我们在max_数组二分查找就可以了。

否则，我们判断sum[n]的正负，如果sum[n]非正，说明无论如何加和都无法到达q，答案为-1。

如果sum[n]大于0，那么我们可以写出如下式子
k*sum[n]+max_[i]>=q

其中k为(q-max_[i])/sum[n]
显然，我们应当将k最小化，那么max_[i]应取最大，我们可以直接取max_[n]
这里除法应为向上取整

那么此时max_[i]>=q-k*sum[n]
二分搜索即可
答案不要忘记加上k *n

教训/收获

向上取整除法n/m=(n-1)/m+1=(n-1+m)/m

代码

#include<cstdio>
#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib> 
#include<chrono>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
#define int long long
//#define double long double
using namespace std;typedef long long ll;const int maxn=200505;int n,m,k;int sum[maxn],max_[maxn];int a[maxn];struct custom_hash {static uint64_t splitmix64(uint64_t x) {x += 0x9e3779b97f4a7c15;x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;x = (x ^ (x >> 27)) * 0x94d049bb133111eb;return x ^ (x >> 31);}size_t operator()(uint64_t x) const {static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();return splitmix64(x + FIXED_RANDOM);}};signed main(){IOS#ifndef ONLINE_JUDGEfreopen("D:\\_ACM_code\\IO\\in.txt","r",stdin);freopen("D:\\_ACM_code\\IO\\out.txt","w",stdout);#endifint tn;cin>>tn;while(tn--){cin>>n>>m;memset(sum,0,sizeof sum);memset(max_,0,sizeof max_);for(int i=1;i<=n;i++){int t;cin>>t;sum[i]+=t;sum[i]+=sum[i-1];}for(int i=1;i<=n;i++){max_[i]=max(max_[i-1],sum[i]);}for(int i=1;i<=m;i++){int q;cin>>q;if(q<=max_[n])cout<<lower_bound(max_+1,max_+1+n,q)-max_-1<<' ';else{if(sum[n]<=0){cout<<"-1"<<' ';continue;}int k=(q-max_[n]-1)/sum[n]+1;q-=k*sum[n];cout<<lower_bound(max_+1,max_+1+n,q)-max_-1+k*n<<' ';}}cout<<endl;}}