Shopping in Mars (25)

/*
1.因为是求区间和 可以采用前缀和的思想 
s[i]=s[i-1]+a[i]
这样在求[l,r]之间的值的时候
s[r]-s[l-1]即可
2.由于对于s[n]这个数组是满足单调性的
故可以用双指针算法
设置l=0,r=0
if(s[r]-s[l-1]>tar)l++;//i向右走 这个区间和就会变小
else if(s[r]-s[l-1]<tar)r++;太小了 r向右走
else

    printf("%d-%d\n",l,r);
    l++;
    r++;
*/
#include <iostream>
(720)#include <algorithm>
#include <cstdio>
(802)#include <limits.h>
using namespace std;
const int N =100010;
int a[N],s[N];
int main()
{
    int n,tar;
    cin>>n>>tar;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        s[i]+=s[i-1]+a[i];
    }
    int l=1,r=1;
    while(l<=n&&r<=n)
    {
        if(s[r]-s[l-1]>tar)l++;
        else if(s[r]-s[l-1]<tar)r++;
        else
        {
            printf("%d-%d\n",l,r);
            l++;
            r++;
        }
    }
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
int s[100010];
int main(){
    int x,y,neary=100000010;
    cin>>x>>y;
    s[0]=0;
    for(int i=1;i<=x;i++){
        cin>>s[i];
        s[i]+=s[i-1];
    }
    for(int i=1;i<=x;i++){  //枚举左端点
        int j=lower_bound(s+i,s+x+1,s[i-1]+y)-s;      //求右端点
        if(s[j]-s[i-1]==y)
            neary=y;
        else if(s[j]-s[i-1]>=y && s[j]-s[i-1]<neary)  //有大于y的解并小于neary
            neary=s[j]-s[i-1];
    }
    for(int i=1;i<=x;i++){
        int j=lower_bound(s+i,s+x+1,s[i-1]+neary)-s;  //找出所有等于neary的区间
        if(s[j]-s[i-1]==neary)
            cout<<i<<"-"<<j<<'\n';
    }
    return 0;
}

思路

利用前缀和数组和双指针找符合条件的值并成对按i的大小存入vector容器，最后讲容器中的值成对输出即可，pat测试最长时间44ms.

代码(c++)

#include <cstdio>
(802)#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 100010;
const int INF = 0x3fffffff;

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    int v[maxn], sum[maxn]; //sum存储前缀和
    v[0] = 0, sum[0] = 0;
    int temp; //临时变量
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &temp);
        v[i] = temp;
        sum[i] = sum[i - 1] + v[i];
    }
    int minCost = INF; //存储找到的最小值
    vector<int> ans;   //结果容器
    int i = 0, j = 0;
    while (i <= (n - 1) && j <= n)
    {
        if ((sum[j] - sum[i]) < m)
        {
            j++;
            continue;
        }
        if (sum[j] - sum[i] < minCost)
        {
            minCost = sum[j] - sum[i];
            ans.clear(); //找到更接近的值，清空容器重新计数
            ans.push_back(i + 1);
            ans.push_back(j);
            i++;
            continue;
        }
        else if (sum[j] - sum[i] == minCost)
        {
            ans.push_back(i + 1); //相同值添加进结果
            ans.push_back(j);
            i++;
            continue;
        }
        i++;
    }
    for (int i = 0; i + 1 < ans.size(); i += 2)
    {
        printf("%d-%d\n", ans[i], ans[i + 1]);
    }
    return 0;
}

/*滑动窗口思想*/
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int>P;
const int AX = 1e5 + 66 ;
int a[AX] ; 
vector<P>res;
int main(){
	int n , m ; 
	scanf("%d%d",&n,&m);
	for( int i = 1 ; i <= n ; i++ ){
		scanf("%d",&a[i]);
	}
	int st = 1 , ed = 1 ;
	int dv = INF ; 
	int sum = 0 ; 
	while( st <= ed ){
		while( ed <= n && sum < m ) sum += a[ed++] ;  
		if( sum < m ) break ; 
		if( dv > sum - m ){
			dv = sum - m ; 
			res.clear() ; 
			res.push_back(P(st,ed-1));
		}else if( dv == sum - m ){
			res.push_back(P(st,ed-1));
		}
		sum -= a[st++] ; 
	}
	for( auto x : res ){
		printf("%d-%d\n",x.first,x.second);
	}
	return 0 ; 
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
typedef long long LL;
LL sum[N],nearest = 1e3+10;//前缀和，最短差距
vector<pair<int,int> > nearV;
int binSearch(int l, int r, LL x){//在[l,r]找大于等于x的下标
    while(l<r){
        int mid = (l+r)>>1;
        if(sum[mid]>=x) r = mid;
        else l = mid + 1;
    }
    if(sum[l]<x) return l+1;//查找失败
    return l;
}
int main(){
    int n,res,x,flag = 0;
    scanf("%d%d",&n,&res);
    for(int i = 1; i <=n; i++){
        scanf("%d",&x);
        sum[i] = sum[i-1] + x;
    }
    for(int i = 1; i <= n; i++){
        //int j = lower_bound(sum+i,sum+n+1,sum[i-1]+res)-sum;
        int j = binSearch(i,n,sum[i-1]+res);
        if(j>n) continue;//查找失败
        LL gap = sum[j]-sum[i-1]-res;
        if(gap==0){
            flag = 1;
            printf("%d-%d\n",i,j);
        }
        else if(gap <= nearest){
            if(gap == nearest) nearV.push_back(make_pair(i,j));
            else {
                nearest = gap;
                nearV.clear(), nearV.push_back(make_pair(i,j));
            }
        }
    }
    if(!flag){
        for(auto p:nearV){
            printf("%d-%d\n",p.first,p.second);
        }
    }
    return 0;
}

题目大意：在一串数字A中找到和为指定和m的区间，如果没有找到，则输出距离指定和相差最小的区间。
采用Two Pointers方法，预处理这一串数字得到前n项和，设立两个指针i,j，如果Asum[i..j] == m,则找到目标，记下该区间，否则Asum[i..j] > m，则记下区间以备最后“没有找到和相等于m的情况时输出”，i自增，因为此时Asum[i+1..j]一定是小于m的，则j不用变，但是i自增后有可能大于j，不要忘记将其指向i

Code

#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 100100;
const int INF = 0x3fffffff;
int n, m;
int acusum[maxn];
vector<pair<int, int> > pairs;
vector<pair<int, int> > bak;

int main() {
    fill(acusum, acusum + maxn, 0);
    scanf("%d %d", &n, &m);
    int temp, min = INF;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &temp);
        acusum[i] = acusum[i - 1] + temp;
    }
    int i = 1, j = 1;
    while (i <= j && i <= n && j <= n) {
        while (acusum[j] - acusum[i - 1] < m && j <= n) {
            j++;
        }
        if (acusum[j] - acusum[i - 1] == m) {
            pairs.push_back(make_pair(i, j));
        } else {
            if ((int)abs((double)acusum[j] - (double)acusum[i - 1]) < min) {
                min = (int)abs((double)acusum[j] - (double)acusum[i - 1]);
                bak.clear();
                bak.push_back(make_pair(i, j));
            } else if ((int)abs((double)acusum[j] - (double)acusum[i - 1]) == min) {
                bak.push_back(make_pair(i, j));
            }
        }
        i++;
        if (j < i) {
            j = i;
        }
    }
    if (pairs.size() != 0) {
        for (int i = 0; i < pairs.size(); i++) {
            printf("%d-%d\n", pairs[i].first, pairs[i].second);
        }
    } else {
        for (int i = 0; i < bak.size(); i++) {
            printf("%d-%d\n", bak[i].first, bak[i].second);
        }
    }
    return 0;
}

#include <iostream>
#include <map>

using namespace std;

const int MAXN = 100003;
int dp[MAXN] = {0};
map<int, int> M;

int main()
{     int n,m;     cin>>n>>m;     for(int i=1;i<=n;i++)     {         cin>>dp[i];         dp[i] += dp[i-1];         M[dp[i]] = i;     }     for(int i=1;i<=n;i++)     {         if(dp[i]<m)             continue;         else if(dp[i]==m)             cout<<"1-"<<i<<endl;         else{             int t = dp[i] - m;             if(!M.count(t))                 continue;             else{                 int p = M[t];                 cout<<p+1<<"-"<<i<<endl;             }         }     }     return 0;
}

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

const int Max=1e5+10;
const int INF=INT_MAX;

int main(){
    ios::sync_with_stdio(0);
	int n,m,nears=INF;
	cin>>n>>m;
	int sum[Max];
	sum[0]=0;
	for(int i=1;i<=n;i++){
		cin>>sum[i];
		sum[i]+=sum[i-1];
	}
	for(int i=1;i<=n;i++){
		int j=upper_bound(sum+i,sum+n+1,sum[i-1]+m)-sum;
		if(sum[j-1]-sum[i-1]==m){
			nears=m;
			break;
		}else if(j<=n&&sum[j]-sum[i-1]<nears){
			nears=sum[j]-sum[i-1];
		}
	}
	for(int i=1;i<=n;i++){
		int j=upper_bound(sum+i,sum+n+1,sum[i-1]+nears)-sum;
		if(sum[j-1]-sum[i-1]==nears){
			cout<<i<<'-'<<j-1<<endl;
		}
	}
	return 0;
}

将所有子序列的和，构成一个矩阵

例：

5 13
2 4 5 7 9

矩阵中的数据是有一定的规律的，既从左到右，从下到上递增，可以按照这些数据的规律，寻找答案

由于数据最大有100000个，使用二维矩阵是很不理想的，或许上三角矩阵可以，当然可以模拟这个过程

#include <cstdio>
#include <vector>
using namespace std;
vector<int> res, sum;
int main() {
    int n, m,temp;
    int k = 1;              // 最接近目标的 1-k 序列
    int min = 99999999;     // 最接近目标的最小序列和
    scanf("%d %d", &n, &m);
    sum.resize(n + 1);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &temp);
        sum[i] = sum[i - 1] + temp; // 保存 1-i 的序列和
        if (sum[i]<m){              // 寻找最接近目标的序列和
            k=i;
        }
    }
    /* sum[k]有两种情况，一种是小于目标值，一种是刚好等于目标值*/
    if (sum[k] < m) {
        k++;        // 小于的时候，不满足题目要求，需要一个比目标值大的数
    }
    /* 1-k 的序列和最接近目标值*/
    temp = min=sum[k];
    int i = 1, j = k;
    while (i <= n && j <= n) {
        if (temp < m) {     // 小于目标值，往右搜索
            temp = sum[++j] - sum[i - 1];
            continue;
        }
       /*有更合适的选择或者相同的选择*/
        if (temp <= min) {
            if (temp < min) {   // 有更合适的序列 更新
                min = temp;
                res.clear();
            }
            /*加入到结果集*/
            res.push_back(i);
            res.push_back(j);
        }
        temp = sum[j] - sum[i++];   // 下移
    }
    for (int t = 0; t < res.size(); t += 2) {
        printf("%d-%d\n", res[t], res[t + 1]);
    }
    return 0;
}

//开始想用dp，不知道咋用，参照了一下别人的思路
//dp[i]表示当前最接近M的连续序列和，用start数组存下标起始位置，
//dp[i+1]=dp[i]+values[i],if(dp[i+1]>M),则需要回退。
//当dp[i]<M时，dp[i]不变，当dp[i]>M时，需要减去从下标start开始的values[start]，直到找到一个start使
//从它开始到i的这一串钻石价值是最近M的（>=M）
#include<iostream>
(720)#include<vector>
#include<algorithm>
(831)#include<limits.h>
using namespace std;
typedef pair<int, int>PP;
const int maxn = 100001;
int main() {
	int m, n;
	cin >> n >> m;
	int values[maxn] = { 0 };
	int start = 1;
	int dp[maxn] = { 0 };
	vector<PP>answer;
	int min = INT_MAX;
	for (int i = 1; i <= n; i++) {
		cin >> values[i];
		if (i == 1) {
			dp[i] = values[i];
		}
		else {
			dp[i] = dp[i - 1] + values[i];
		}
		if (dp[i] >= m) {
			while (dp[i] >= m && start <= i) {
				dp[i] = dp[i] - values[start];
				start++;
			}
			start--;
			dp[i] += values[start];
			if (dp[i] - m == min) {
				answer.push_back(PP(start, i));
			}
			else if (dp[i] - m < min) {
				answer.clear();
				min = dp[i] - m;
				answer.push_back(PP(start, i));
			}
		}
	}
	sort(answer.begin(), answer.end());
	for (int i = 0; i < answer.size(); i++) {
		printf("%d-%d\n", answer[i].first, answer[i].second);
	}
}

a,b = list(map(int,input().split(' '))),list(map(int,input().split(' ')))
i = 0;j = 1;m = 10 ** 10;n = [];f = 1

while j < a[0] + 1:
    if sum(b[i:j]) < a[1]:
        j += 1
    elif sum(b[i:j]) > a[1]:
        if f:
            if m > sum(b[i:j]):
                m = sum(b[i:j]);n.clear()
                n.append(str(i + 1) + '-' + str(j))
            elif m == sum(b[i:j]):
                n.append(str(i + 1) + '-' + str(j))
        i += 1
    else:
        print(str(i + 1) + '-' + str(j))
        f = 0;i += 1;j += 1

if f:
    for i in n:
        print(i)

a,b = list(map(int,input().split(' '))),list(map(int,input().split(' ')))
i = 0;j = 1;m = 10 ** 10;n = [];f = 1;p = b[0]

while j < a[0]:
    if p < a[1]:
        p += b[j];j += 1
    elif p > a[1]:
        if f:
            if m > p:
                m = p;n.clear()
                n.append(str(i + 1) + '-' + str(j))
            elif m == p:
                n.append(str(i + 1) + '-' + str(j))
        p -= b[i];i += 1
    else:
        print(str(i + 1) + '-' + str(j))
        f = 0;p +=b[j] - b[i];i += 1;j += 1

while p > a[1]:
    if f:
        if m > p:
            m = p;n.clear()
            n.append(str(i + 1) + '-' + str(j))
        elif m == p:
            n.append(str(i + 1) + '-' + str(j))
    p -= b[i];i += 1
    
else:
    if p == a[1]:f = 0;print(str(i + 1) + '-' + str(j))

if f:
    for k in n:
        print(k)

#include<iostream>
#include<stdio.h>
#include<map>
using namespace std;
const int maxn = 100009;
map<int, int>simap;
int  input[maxn];
int main(){
    int n, sum,tsum=0;
    //get input data
    scanf("%d%d", &n, &sum);
    for (int i = 1; i <= n; i++){
        scanf("%d", &input[i]);
        tsum += input[i];
        input[i] = tsum;
        simap[tsum] = i;
    }
    //print the answer
    for (int i = 1; i <= n; i++){
        if (input[i] == sum){
            cout << 1 << "-"<<i << endl;
            continue;
        }
        int last = simap[input[i] - sum];
        if ( last == 0) continue;
        cout << last+1 << "-"<< i << endl;
    }
    return 0;
}