zstu 4247 单调栈

Description

 zstu的萌新们准备去自助旅行，他们租了一辆吉普车，然后选择了n个城市作为游览地点。然后他们惊喜的发现他们选择的城市刚好绕城一个环。

   也就是说如果给所有城市按照0,1,2,……,n-1编号，0号城市和n-1号城市是相邻的，并且只能从i号城市去(i+1)%n号城市。

已知每个城市可以充油gas(i),从 i 到 (i+1)%n 城市耗油 cost(i)。

   假设这辆吉普车没有的油箱一开始是空的，并且没有上限。

   没有油的话自然就不能继续旅行了，这个问题让萌新们非常困扰。作为优秀的acmer，请你帮他们找到一个出发城市，使得萌新们能游览尽可能多的城市（注意最多游览n个城市）。如果有多个可选择的出发城市，那么请把他们按照编号从小到大输出。

Input

第一行有个整数T, 表示测试组数。T≦10。

接下来的每个测试组第一行有个数n, 表示游览的城市数, 2 <= n <= 100000。

第二行有n个数， 第i个数表示在i号城市能充油gas(i)，0 <= i <= n-1。

第三行有n个数，第i个数表示从i号城市到(i+1)%n号城市会耗油  cost(i), 0 <= i <= n-1,  0 <=  gas(i), cost(i) <= 10000。

Output

对于每个测试组，请在一行中输出可以选择的出发城市编号，并按照编号从小到大输出。

Sample Input

2

2

4 4

5 3

2

2 3

3 4

Sample Output

1

0 1

官方题解 ：

方法大体是首先求一个pre(i)为segma(0<=j<=i) gas(i)-cost(i)
为了方便处理，我们把n开两倍，
我们用线段树维护区间区间min{pre(i)}
然后对于每一个位置i，我们要找到i这个位置能跑到多远，就等效于
找到一个pre(j), 使得pre(j)

用单调栈  复杂度O(n)

ps：我懒得去算有多少个数  所以先输出空格  再输出\b（回格）  然后无限WA。。。

#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
ll gas[200005],cost[200005],ans[200005];
struct node{ll num,lab;
}e[200005];
stacksp;
int main(){ll t;scanf("%lld",&t);while(t--){while(!sp.empty())sp.pop();ll n,i,j;scanf("%lld",&n);for(i=1;i<=n;i++)scanf("%lld",&gas[i]);for(i=1;i<=n;i++)scanf("%lld",&cost[i]);for(i=n+1;i<=2*n;i++){gas[i]=gas[i-n];cost[i]=cost[i-n];}for(i=1;i<=2*n;i++){e[i].num=e[i-1].num+gas[i]-cost[i];e[i].lab=i;}e[2*n].lab=2*n;e[2*n].num=1;for(i=1;i<=31;i++)e[2*n].num*=2;e[2*n].num*=-1;sp.push(e[2*n]);for(i=2*n-1;i>=n;i--){while(e[i].num<=(sp.top()).num)sp.pop();sp.push(e[i]);}ll sj=0,l=0;for(i=n-1;i>=0;i--){while(e[i].num<=(sp.top()).num)sp.pop();node f=sp.top();sp.push(e[i]);ans[i]=min(f.lab-i,n);sj=max(ans[i],sj);}for(i=0;i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！