A1044 Shopping in Mars (25 分)

一、技术总结

可以开始把每个数都直接相加当前这个位置的存放所有数之前相加的结果，这样就是递增的了，把i，j位置数相减就是他们之间数的和。
需要写一个函数用于查找之间的值，如果有就放返回大于等于这个数的右下标，函数中采用引用的传参方式，就不需要返回值了。
在处理存放下标问题上，如果发现有更小的数时，直接清空之前存放的值。

二、参考代码

#include<algorithm>

#include<iostream>

#include<vector>

using namespace std;

int n, m;

vector<int> sum, result;

void Func(int i, int &j, int &tempsum){

	int left = i, right = n;

	while(left < right){

		int mid = (left + right)/2;

		if(sum[mid] - sum[i-1] >= m){

			right = mid;

		}else{

			left = mid + 1;

		}

	}

	j = right;

	tempsum = sum[j] - sum[i-1];

}

int main(){

	cin >> n >> m;

	sum.resize(n+1);

	for(int i = 1; i <= n; i++){

		scanf("%d", &sum[i]);

		sum[i] += sum[i-1];

	}

	int minans = sum[n];

	for(int i =1; i <= n; i++){

		int j, tempsum;

		Func(i, j, tempsum);

		if(tempsum > minans) continue;

		if(tempsum >= m){

			if(tempsum < minans){

				result.clear();

				minans = tempsum;

			}

			result.push_back(i);

			result.push_back(j);

		}

	}

	for(int i = 0; i < result.size(); i += 2){

		printf("%d-%d\n", result[i], result[i+1]);

	}

	return 0;

}

巴特西

A1044 Shopping in Mars (25 分)

一、技术总结

二、参考代码

最新文章

热门文章