先把d重新计算成第i个点到第i+1个点的距离，d[n]=L-d[1]-...

怎么找到一个可行解呢？
类似求最大连续全0子序列的方法，从某个起点开始不断累计额，如果中途累加的结果<0就断掉此段，在下一个点重启新的一段，当我们一段中的数字个数达到n的时候说明我们找到了一个解，注意到所有S加起来正好等于一圈的长度，所以如果我们起点处s[i]-d[i]>0，那么我们从下一个点走，必定会在走完之前和就变为负的，因此所有的可行起点一定是从第一个可行解的起点开始往下所有连续的s[i]-d[i]==0的点

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
const int N=100000+10;
const int inf=0x3f3f3f3f;
const ll mod=7777777;
const double PI=3.1415926;
const double eps=1e-8;

int n,L;
int s[500001];
int d[500001];
ll res;
int cnt;
vector<int> v;
int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>n>>L;
    ll sum=0;
    FOR(i,n) cin>>d[i]>>s[i],sum+=d[i];
    d[n+1]=L-sum;
    FOR(i,n) d[i]=d[i+1];
    d[n+1]=0;
    FOR(i,2*n) {
        int j=i;
        if (i>n) j-=n; 
        res+=s[j]-d[j];
        ++cnt;
        if (res<0) {
            res=0;
            cnt=0;
        } else if (cnt==n) {
            while (1) {
                if (v.size()==n) break;
                int x=i-n+1;
                int j=i;
                if (i>n) j-=n;
                if (x<=0) x+=n;
                v.pb(x);
                if (s[x]-d[x]==0) i++;
                else break;
            }
            break;
        }
    }
    if (v.size()==0) cout<<-1<<endl;
    else {
        sort(v.begin(),v.end());
        for (int i=0;i<v.size();i++) cout<<v[i]<<" ";
        cout<<endl;
    }
    return 0;
}

首先，我们可以用S[1][i]表示由第1个加油站开始开到第i个加油站途中把1~i-1加油站的油全加了，然后油箱所剩的油为多少（从1出发到i的净剩油量，其值可能小于0），找到s[1][1]~s[1][n]里面的最小值，如果最小值大于0表示可以从1出发最后回到1。
然后你会惊讶的发现，选择i作为起点，与选择1作为起点的不同之处就在于
s[i][j]=s[1][j]-s[1][i];
而对于同一个出发点i,s[1][i]是一个确定的值，所以
min(s[i][i]~s[i][i-1])=min(s[1][1]~s[1][n])+s[1][i]。
也就是说我们只需要找一次s[1][1~n]的最小值，然后加上s[1][i]如果大于等于0那么i就可以作为起点。数组的第一维始终是1，所以可以省掉得到以最终的式子：
ans=min(s[1~n]);
for(i=1;i<=n;i++)
if (ans+s[i]>=0) i可以作为起点。
C++代码如下：
#include<iostream>
using namespace std;
int v[500000],c[500000];
int s[500000]={0};
int n,l,ans=0;
int main()
{
cin>>n>>l;
int i,a,b;
for (i=0;i<n;i++) cin>>v[i]>>c[i];
for (i=1;i<n;i++) {s[i]=s[i-1]+c[i-1]-v[i];if (ans>s[i])ans=s[i];}
l=0;
for (i=0;i<n;i++)
if (ans-s[i]>=0) v[l++]=i+1;
if (l>0)
{
for(i=0;i<l-1;i++) cout<<v[i]<<" ";
cout<<v[l-1]<<endl;
} else cout<<-1<<endl;

}

var
a,b,c:array [0..500005] of longint;
n,l,i,min,t:longint;
begin
readln(n,l);
for i:=1 to n do read(a[i],b[i]);
for i:=2 to n do c[i]:=c[i-1]-a[i]+b[i-1];
min:=1000000000; t:=0;
for i:=1 to n do if (c[i]<min) then min:=c[i];
for i:=1 to n do if (c[i]=min) then
if (t=0) then begin write(i); t:=1; end else write(' ',i);
writeln;
end.

只需研究每条路上油料净收入即可。

最大子串和的第一个数铁定合法，然后从这个数开始到某个数，和正好为0，那么那个数之后的那个数也合法。

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <limits>
using namespace std;

int n,l,minr,sum[500000];
int d[500000+1],s[500000+1];
int sumd[500000+1],sums[500000+1];

int calcd(int x,int y)//當x=y時，不是環繞一圈
{
    if (x<=y)
        return sumd[y]-sumd[x];
    else
        return calcd(x,n)+calcd(0,y);
}

int calcs(int x,int y)
{
    if (x==y)//不加油
        return 0;
    else if (x<y)
    {
        if (x==0)
            return sums[y-1];
        else
            return sums[y-1]-sums[x-1];
    }
    else if (x>y)
        calcs(x,n)+calcs(0,y);
}

int main()
{
    while (~scanf("%d%d",&n,&l))
    {
        for (int i=0;i<n;i++)
            scanf("%d%d",&d[i],&s[i]);
        memset(sumd,0,sizeof(sumd)),memset(sums,0,sizeof(sums));
        sumd[0]=d[0],sums[0]=s[0];
        for (int i=1;i<n;i++)
            sumd[i]=sumd[i-1]+d[i],sums[i]=sums[i-1]+s[i];
        d[n]=l-sumd[n-1],sumd[n]=l,s[n]=0,sums[n]=sums[n-1];
        for (int i=0;i<n;i++)
            sum[i]=calcs(0,i)-calcd(0,i);
        minr=sum[0];
        for (int i=1;i<n;i++)
            minr=min(minr,sum[i]);
        for (int i=0;i<n;i++)
            if (minr==sum[i])
                printf("%d ",i+1);
        printf("\n");
    }
}

一定要加读入优化！

#include <algorithm>
#include <cstdio>

using namespace std;

#define rep(id,from,to) for (int id = (from); id <= (to); id++)

const int maxN = 500005;

int N;
int D[maxN], S[maxN];

inline void read (int* x)
{
(*x) = 0;
char c = 0;
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9')
{
(*x) = (*x) * 10 + c - '0';
c = getchar();
}
}

void input()
{
read (&N);
int dum;
read (&dum);
rep (i, 1, N)
{
read (D + i);
read (S + i);
}
}

void solve()
{
int tot (0);
int mn (0);
rep (i, 2, N)
{
tot += (S[i - 1] - D[i]);
mn = min (mn, tot);
}
if (mn == 0) printf ("1 ");
int offset (0);
rep (i, 2, N)
{
offset += (D[i] - S[i - 1]);
if (mn + offset >= 0) printf ("%d ", i);
}
}

int main()
{
input();
solve();
return 0;
}

玛德，难道我是祖传的常数大吗？今天已经是第二次加了输入挂才A掉。。2333
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}

const int N = 500000 + 5;

int n, L, d[N], s[N], a[N << 1], sum[N << 1], q[N << 1];
int cnt, ans[N];

int main() {
n = read(), L = read();
int tmp = 0;
d[n] = read(), s[1] = read();
for (int i = 2; i <= n; i++) {
d[i - 1] = read(), s[i] = read();
tmp += d[i - 1];
}
d[n] = L - tmp;
for (int i = 1; i <= n; i++) a[i] = s[i] - d[i];
for (int i = 1; i <= n - 1; i++) a[n + i] = a[i];
for (int i = 1; i <= n * 2 - 1; i++) sum[i] = sum[i - 1] + a[i];
int h = 0, t = 0;
for (int i = 1; i <= n - 1; i++) {
while (h < t && sum[i] <= sum[q[t - 1]]) t--;
q[t++] = i;
}
for (int i = n; i <= n * 2 - 1; i++) {
while (h < t && q[h] <= i - n) h++;
while (h < t && sum[i] <= sum[q[t - 1]]) t--;
q[t++] = i;
if (sum[q[h]] - sum[i - n] >= 0) ans[++cnt] = i - n + 1;
}
if (!cnt) printf("-1\n");
else {
for (int i = 1; i <= cnt - 1; i++) printf("%d ", ans[i]);
printf("%d\n", ans[cnt]);
}
return 0;
}

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAXN=500000 + 10;

int d[MAXN],s[MAXN],lim[MAXN];

int main()
{
int n,l;
scanf("%d%d",&n, &l);
int sum=0;
for(int i=1; i<=n; i++){
scanf("%d%d",&d[i-1],&s[i]);
sum += d[i-1];
}

d[n] = l-sum;

int f = 100000001, b=0;
int flag = 0;

for(int i=1; i<=n; i++){
lim[i] = s[i]-d[i];
b += lim[i];
f = min(f, b);
}
for(int i=1; i<=n; i++){
f -= lim[i-1];
if(f >= 0){
printf("%d ",i);
flag=1;
}
}
if(flag == 0)
printf("-1");
return 0;

}
注意输入输出！！！！！！！！！！！！
不要用cin ，cout！！！！！！！！

program exam10911;
var n,m,i,l,r,tot:longint;
a,s,c,aa,bb:array[0..2000002]of longint;
begin
assign(input,'1.txt');
reset(input);
readln(n,m);
readln(aa[1],bb[1]);
for i:=2 to n do
begin
readln(aa[i],bb[i]);
aa[n+i]:=aa[i]; bb[n+i]:=bb[i];
a[i-1]:=bb[i-1]-aa[i];
a[n+i-1]:=a[i-1];
m:=m-aa[i];
end;
a[n]:=bb[n]-m; a[2*n]:=a[n];
s[0]:=0;
tot:=0;
for i:=1 to n*2 do
s[i]:=s[i-1]+a[i];
for i:=1 to 2*n-1 do
begin
while (l<=r)and(s[i]<s[c[r]]) do
dec(r);
inc(r);
c[r]:=i;
while (l<=r)and(i-n>=c[l])do
inc(l);
if i>=n then
if s[c[l]]-s[i-n]>=0 then
begin
if tot<>0 then write(' ');
write(i-n+1);
inc(tot);
end;
end;
if tot=0 then writeln(-1);
end.

program exam10911;
var n,m,i,l,r,tot:longint;
a,s,c,aa,bb:array[0..2000002]of longint;
begin
assign(input,'1.txt');
reset(input);
readln(n,m);
readln(aa[1],bb[1]);
for i:=2 to n do
begin
readln(aa[i],bb[i]);
aa[n+i]:=aa[i]; bb[n+i]:=bb[i];
a[i-1]:=bb[i-1]-aa[i];
a[n+i-1]:=a[i-1];
m:=m-aa[i];
end;
a[n]:=bb[n]-m; a[2*n]:=a[n];
s[0]:=0;
tot:=0;
for i:=1 to n*2 do
s[i]:=s[i-1]+a[i];
for i:=1 to 2*n-1 do
begin
while (l<=r)and(s[i]<s[c[r]]) do
dec(r);
inc(r);
c[r]:=i;
while (l<=r)and(i-n>=c[l])do
inc(l);
if i>=n then
if s[c[l]]-s[i-n]>=0 then
begin
if tot<>0 then write(' ');
write(i-n+1);
inc(tot);
end;
end;
if tot=0 then writeln(-1);
end.

/*
好奇妙的做法啊QAQ
根本想不通为啥想了半天
用sum[i]表示由第1个加油站开始开到第i+1个加油站途中把1~i加油站的油全加了
然后油箱所剩的油为多少
sum[i]有可能<0,且显然sum[0]与sum[n]都等于0,然后找出t=min(sum[i]){i=1..n}
..那么当sum[x-1]=t时,x就是其中1个答案[x=1..n] 
证明：
a[i]--站点i的油所能走的距离-i到站点i+1的距离
当sum最小则,a[i]+a+..a[n]=-sum(因为a[1]+...+a[i]要为sum而和为0)
则可知道.a[i]+a+..a[k]>0对于任意(i<=k<=n)必然成立
否则sum不为最小值..所以当sum[x-1]=t时x就为一解

这种方法好像是最简单但是很难想到的吧
还有单调队列 O(n)的动规算法等
对于环我们可以把它复制粘在后面。
然后我们对于每一个加油站，设置一个a[]表示在这一个加油站加的油减去从这个加油站开到另一个加油站的差。
那么我们要想选定某个加油站i作为起点，问题就变成了从i到i+n能够中间不断油，不断油的表现就是对于路径上的任何一个
加油站k，有a[i]+a[i+1]...+a[k]>0，我们维护一个前缀和s[i]=a[1]+a[2]+a[3]+...a[i]，那么a[i]+a[i+1]+..+a[k]=
s[k]-s[i-1]，我们枚举加油点i作为起点，那么我们的问题就是检验i<k<=i+n，都有s[k]-s[i-1]>0，这个问题只要我们检验s[k]中的最小值就可以解决了。那么s[k]的最小值可以用什么迅速求呢？单调队列！它的均摊复杂度就是O(1)的...然后
我们直接枚举1~n-1的每一个加油站作为起点，然后从它的区间里面用单调队列找出最小值，判断它们的差是否大于0即可。
O(n)的动归。

由于是个环，先把他复制一遍放到后面。然后，第i个点能环游的条件是能从这点走到第i+n点。

我们设一个函数f[i]=(k,left)表示从第i个点向后走最多能走到第k个点，并剩下可走left长度的油。

显然，i能环游的条件是f[i].k>=i+n

下面是状态转移。
1：先置k=i表示当前在k处。再置left=s[i]表示当前剩余油量。
2：如果left<D[k+1]那么就是说当前油量不够走到下一个节点，跳出循环。
　　否则：
　　　　left:=left-D[k+1]+f[k+1].left //先走到k+1处然后从k+1点向后走
　　　　k:=f[k+1].k //在k+1点时按f[k+1]的走法走。
　　然后，由于可能当前剩余油量仍够继续走下去，所以重复第2步。

循环结束后的k就是从i点最多能向后达到的节点编号，left为剩余油量。

算法复杂度：
在转移f[i]时，我们把f,f等作为一个整体来考虑，相当于将i+1,i+2……n分成了几个块，然后每个块最多处理一次。
设h[i]表示转移f[i]时向后走过了h[i]个块，即合并了h[i]个块。
再设g[i]表示在算f[i]时,i到n之间被划分成了g[i]个块。
那么g[i]=g+1-h
即：g-g[i]=h-1
所以g[n]=∑h[i]-n
由于g[n]=0，所以，∑h[i]=n
故总的复杂度为O(n)。
*/
#include <iostream>
using namespace std;

const int MAXN=500005;
int n,L;
int d,s;
int sum[MAXN];
int Min=0x7fffffff;

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>L;
    if(n==1)
    {
        cout<<1<<endl;
        return 0;
    }
    cin>>d;
    for(int i=2;i<=n;i++)
    {
        cin>>s>>d;
        sum[i]=sum[i-1]+s-d;
        if(sum[i]<Min)  Min=sum[i];
    }
    for(int i=1;i<=n;i++)
        if(sum[i]==Min)
            cout<<i<<" ";
    return 0;
}
     

楼上的 你们..想多了
#include <cstdio>
#define MAXN 500005
int cd[MAXN];
int n,l;
int main()
{
int si,di,mincd=1000000050;
scanf("%d%d",&n,&l);
if(n==1){printf("1");return 0;}

scanf("%d",&di);
for(int i=2;i<=n;i++)
{
scanf("%d%d",&si,&di);
cd[i]=cd[i-1]+si-di;
if(cd[i]<mincd) mincd=cd[i];
}
scanf("%d",&si);

for(int i=1;i<=n;i++)
if(cd[i]==mincd)
printf("%d ",i);
return 0;
}

program exam10911;
var n,m,i,j,k,x,y,l,r,tot:longint;
a,s,c:array[0..1000002]of longint;
aa,bb:array[0..1000001]of longint;
begin
readln(n,m);
readln(aa[1],bb[1]);
for i:=2 to n do
begin
readln(aa[i],bb[i]);
aa[n+i]:=aa[i]; bb[n+i]:=bb[i];
a[i-1]:=bb[i-1]-aa[i];
a[n+i-1]:=a[i-1];
m:=m-aa[i];
end;
a[n]:=bb[n]-m; a[2*n]:=a[n];
s[0]:=0;
tot:=0;
for i:=1 to n*2 do
s[i]:=s[i-1]+a[i];
for i:=1 to 2*n-1 do
begin
while (l<=r)and(s[i]<s[c[r]]) do
dec(r);
inc(r);
c[r]:=i;
while (l<=r)and(i-n>=c[l])do
inc(l);
if i>=n then
if s[c[l]]-s[i-n]>=0 then
begin
if tot<>0 then write(' ');
write(i-n+1);
inc(tot);
end;
end;
if tot=0 then writeln(-1);
end.

注意特判n=1的情况..咱的单调队列是水不过的...
对于环我们可以把它复制粘在后面。
然后我们对于每一个加油站，设置一个a[]表示在这一个加油站加的油减去从这个加油站开到另一个加油站的差。
那么我们要想选定某个加油站i作为起点，问题就变成了从i到i+n能够中间不断油，不断油的表现就是对于路径上的任何一个
加油站k，有a[i]+a[i+1]...+a[k]>0，我们维护一个前缀和s[i]=a[1]+a[2]+a[3]+...a[i]，那么a[i]+a[i+1]+..+a[k]=
s[k]-s[i-1]，我们枚举加油点i作为起点，那么我们的问题就是检验i<k<=i+n，都有s[k]-s[i-1]>0，这个问题只要我们检验s[k]中的最小值就可以解决了。那么s[k]的最小值可以用什么迅速求呢？单调队列！它的均摊复杂度就是O(1)的...然后
我们直接枚举1~n-1的每一个加油站作为起点，然后从它的区间里面用单调队列找出最小值，判断它们的差是否大于0即可。
复杂度就是O(N)的了，具体可看:
http://acm.hdu.edu.cn/showproblem.php?pid=4193
HDU那题网上题解很多...表示弱菜是看了题解很久之后才弄懂该怎么做的...

呵呵。。暴力过的路过

单调队列优化

#include

#include

#include

#define MAXN 1000001

using namespace std;

int N , L ;

int next[MAXN] , add[MAXN] , a[MAXN] , s[MAXN] ;

struct data

{

int s , num ;

}

q[MAXN] ;

int main()

{

scanf("%d%d",&N,&L);

scanf("%d%d",&next[N],&add[1]);

int tot = 0 ;

for (int i = 2 ; i

类似今天普及组完善程序第1题

不存在包含关系的区间、存在单调性

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 306ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：306ms

Accepted 有效得分：100 有效耗时：25ms

队列维护速度快。。。