题意是给你n个数 组成的环 求以一个数开头 的数列所有前缀都为非负数的数列的个数:
思路: 先扩展成2*n的数列 然后求出sum【i】表示前i项的和 对每个i>.=n结尾的数列 只要单调队列里的最小值大于等于sum【i-n】就满足情况(想想为什么) 对于单调队列 只要维护长度大于等于n 递增的就行;
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int num[2001000],sum[2001000],id[2001000];
int main()
{
int n,i,j;
while(~scanf("%d",&n),n)
......
阅读全文