PAT甲級_1044 Shopping in Mars (25 分)

題目描述

思路：

值非負，故從1到i的累加數組遞增，左端點枚舉右端點二分，整體複雜度O(nlogn)

代碼：

#include <bits/stdc++.h>
using namespace std;

int sum[100010];//a[i]非負故sum[i]遞增 

int main()
{
	int n, m;
	cin>>n>>m; 
	for(int i=1;i<=n;i++){//為便于輸出使i從1起 
		cin>>sum[i];
		sum[i] += sum[i-1];//讀入時直接累加 
	}
	int min = INT_MAX;
	for(int i=1;i<=n;i++){//先确定需要湊出的數 
		int j = lower_bound(sum+i, sum+n, sum[i-1]+m) - sum;//注意寫法 
		if(sum[j]-sum[i-1]==m){
			min = m;
			break;
		}else//若沒有>=m的則j會是數組末尾
			if(sum[j]-sum[i-1]>m&&sum[j]-sum[i-1]<min&&j<=n) min = sum[j]-sum[i-1];
	}
	for(int i=1;i<=n;i++){//再确定組合 
		int j = lower_bound(sum+i, sum+n, sum[i-1]+min) - sum;
		if(j<=n&&sum[j]-sum[i-1]==min) cout<<i<<'-'<<j<<endl; 
	} 
	return 0;
}