题意:你带着K元要去n个城市,这n个城市是环形的,你可以选择任意一个起点,然后顺时针走,对于每个城市,到达时可以获得a元,但是从这里离开又需要花费b元,问你能否找到一个起点(输出花钱最少的那个),使得你能够走完一圈,不能输出-1
题解:首先对于环形问题,先把数组复制一次,现在从每个起点开始,满足条件的点就肯定可以进队,其实我们要求的一个i满足,从i到n+i的所有前缀和最小值一定要大于K,因为对于1个i只会进队一次出队一次,所以尺取一下
(我们一路判断的就是,带着K元能不能加上这段区间>=0,不能的话起点就要顺延,同时终点也顺延,每次只改变头首2个元素)
#include<bits/stdc++.h>
#define N 2000010
using namespace std;
int T,ans,n,m,cnt,b[N],a[N],c[N];
int main()
{
scanf("%d",&T);
while (T--)
{
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++) scanf("%d",&a[i]);
for (int i=;i<=n;i++) scanf("%d",&b[i]);
for (int i=;i<=n;i++)
{
c[i]=a[i]-b[i];
c[i+n]=c[i];
}
int l=,r=;
long long ans=;
while (l<=n && r-l+<=n)
{
ans+=c[r];
r++;
while (ans+m<)
{
ans-=c[l];
l++;
}
}
if (l>n) printf("-1\n");else printf("%d\n",l);
}
return ;
}
比赛时,队友为了实现类似想法,却苦于没听过尺取(我也没听过),和不是很能确定a[i]和b[i]是否能统一的问题,大力码的2种。
#include<bits/stdc++.h>
using namespace std;
#define mem(a,i) memset(a,i,sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define lowbit(x) (x&-x)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> pii;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int maxn=1e6+;
ll a[maxn*];
ll b[maxn*];
int n;
ll sum;
int main() {
int caseCnt;
scanf("%d",&caseCnt);
while(caseCnt--) {
scanf("%d%lld",&n,&sum);
rep(i,,n-) scanf("%lld",&a[i]);
rep(i,n,*n-) a[i]=a[i-n];
rep(i,,n-) scanf("%lld",&b[i]);
rep(i,n,*n-) b[i]=b[i-n];
int l=;
while(l<n) {
if(sum+a[l]>=) {
break;
}
l++;
}
if(l==n) puts("-1");
else {
int r=l+;
ll res=sum+a[l];
ll temp=res;
bool ok=false;
while(r<*n) {
if(r-l==n) temp=res-b[r-];
else temp=min(res-b[r-],res-b[r-]+a[r]);
if(temp<) break;
if(r-l==n) {
ok=true;
break;
}
res=res-b[r-]+a[r];
r++;
}
if(ok) {
printf("%d\n",l+);
continue;
}
int ans;
while(l<n) {
while(l<r&&temp<) {
temp=temp-a[l]+b[l];
res=res-a[l]+b[l];
l++;
}
res=res-b[r-]+a[r];
if(l==r) {
while(l<n) {
if(sum+a[l]>=) {
break;
}
l++;
}
if(l==n) break;
r=l;
res=sum+a[l];
}
r=r+;
while(r<*n) {
if(r-l==n) temp=res-b[r-];
else temp=min(res-b[r-],res-b[r-]+a[r]);
if(temp<) break;
if(r-l==n) {
ans=l+;
ok=true;
break;
}
res=res-b[r-]+a[r];
r++;
}
if(ok) break;
}
if(!ok) puts("-1");
else {
printf("%d\n",ans);
}
}
}
return ;
}
#include <cstring>
#include <cstdio>
#include<assert.h>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include<iostream>
#include<queue>
#include<functional>
#include <vector>
#include<set>
#include<string>
#include<map>
#include<unordered_set>
using namespace std;
long long a[], b[];
int main() {
long long i, j, k, n, m, l, r, res, t, c, ans;
scanf("%lld", &t);
while (t--)
{
scanf("%lld%lld", &n, &c);
for (i = ; i < n; i++) {
scanf("%lld", &a[i]);
a[n + i] = a[i];
}
for (i = ; i < n; i++) {
scanf("%lld", &b[i]);
b[n + i] = b[i];
}
l = ;
while (l < n&&c + a[l] < )
l++;
if (l == n)
{
printf("-1\n");
continue;
}
r = l; res = c + a[l];
bool ok = false;
while (l < n)
{
bool flag = false;
long long need = b[r];
if (a[r + ] < && r + != (n + l)) {
need -= a[r + ];
flag = true;
}
while (r < (n + l) && res >= need)
{
r++;
res = res - need;
if(!flag)
res = res + a[r];
flag = false;
if (r == (n + l - )) {
need = b[r];
flag = false;
}
else {
need = max(b[r], b[r] - a[r+]);
if (a[r+] < )
flag = true;
}
}
if (r == (l + n))
{
ok = true;
ans = l;
break;
}
res = res - need;
r++;
while (l < r&&res + b[l] - a[l] < ) {
res = res + b[l] - a[l];
l++;
}
if (!flag)
res += a[r];
if (l == r)
{
while (l < n&&c + a[l] < )
l++;
if (l == n)
{
break;
}
else
{
r = l;
res = c + a[l];
}
}
else
{
res = res + b[l] - a[l];
l++;
}
}
if (ok)
{
printf("%lld\n", ans + );
}
else
printf("-1\n");
}
}