蒟蒻站外题求助,十万火急,玄关
  • 板块灌水区
  • 楼主Tsumiki_Mikan
  • 当前回复7
  • 已保存回复7
  • 发布时间2023/7/18 18:15
  • 上次更新2023/11/3 09:04:12
查看原帖
蒟蒻站外题求助,十万火急,玄关
611170
Tsumiki_Mikan楼主2023/7/18 18:15

【问题描述】 小羊们上完课后,纷纷到草场上吃草。而羊村现在正在进行特色示范羊村检查,领导们想看看羊村的草场。 羊村的草场是连续分布的,每块草场上都有数量不等的羊在吃草。领导们想要查看连续若干个草场,但是又不想看到超过T只羊。而村长希望领导们多看看羊村的风貌,尽可能多参观几个草场。 现在,请你帮村长决定,带领导们去参观哪一段草场,满足领导和村长的要求。

【输入】 第一行一个整数N和T,表示羊村共有多少个连续草场,以及领导们希望看到羊数量的最大值。 第二行N个整数,两个整数间用一个空格分开,第i个数ai表示第i个草场上有ai只羊在吃草。编号从1到N。

【输出】 输出一行,共两个数,表示参观的起点编号和终点编号,中间用空格分开。走的方向总是从编号小的到编号大的。另外,若有长度相同的可能性,输出起点编号较小的答案。数据保证至少有答案存在。

样例输入

5 10
6 3 2 1 7

样例输出

2 4

30%的数据,1<=N<=100;

60%的数据,1<=N<=1000;

100%的数据,1<=N<=100000, 0<=ai<=10^9,0<=T<=2^31-1

所以只会暴力的本蒟蒻七十分就挂了

#include<bits/stdc++.h>
using namespace std;
long long n,t,a[100005],f[100005],sum,ans,s,e;
int main(){
	cin>>n>>t;
	cin>>a[1];
	f[1]=a[1];
	for(int i=2;i<=n;i++){
		cin>>a[i];
		f[i]=f[i-1]+a[i];
	}
	for(int i=1;i<=n;i++){
		for(int k=i+1;k<=n;k++){
			if(f[k]-f[i-1]>t) break;
			if(k-i+1>sum){
				sum=k-i+1;
				s=i,e=k;
			}
		}
	}
	cout<<s<<" "<<e;
}

问各位大佬们满分应该怎么写

2023/7/18 18:15
加载中...