はなたの日記

プログラミング(C言語)の勉強をしています。超初心者です。

DSL_3_A The Smallest Window I

問題
The Smallest Window | Sliding Window | Aizu Online Judge

smallest windowを求める問題です。なんじゃそりゃって感じですね。
どうやら尺取り法というアルゴリズムが良いらしいです。初めましてのアルゴリズムだったので、調べました。
考え方はこちらのサイトを参考にしました。確かに区間の動かし方が尺取り虫みたいですね。
尺取り法 | 健忘症の備忘録

久しぶりにC言語でやってみました。

#include<stdio.h>
#define LARGE 100001
#define MIN(a,b) ((a) < (b) ? (a) : (b))

int getAns(int a[],int n,int s){
	int i=0,j=0;
	int sum=0;
	int ans=LARGE;
	
	for(i=1;i<=n;i++){
		sum+=a[i-1];
		if(sum >= s){
			ans=MIN(i-j,ans);
			while(sum >= s){
				sum-=a[j];
				j++;
				if(sum >= s)
					ans=MIN(i-j,ans);
			}
			
		}
	}
	
	if(ans==LARGE)
		ans=0;
	
	return ans;
}


int main(){
	int a[LARGE];
	int n,s;
	int ans=0;
	
	scanf("%d %d",&n,&s);
	
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]);

	printf("%d\n",getAns(a,n,s));
	
	return 0;
	
}

iは幅の右端、jは幅の左端という感じです。半開区間を採用しているので、iは1~nになっています。