1044 Shopping in Mars(25 分)

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 10;
const int INF = 1e9 + 10;
int n, m, a[maxn];
int main()
{
    scanf("%d%d", &n, &m);
    int x;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        a[i] += a[i - 1];
    }
    int mincost = INF, minm = INF;
    sort(a, a + n);
    for (int i = 1; i <= n; i++)
    {
        int j = upper_bound(a + i, a + n+1, a[i-1] + m) - a;
        if (a[j - 1] == a[i-1]+m)
        {
            minm = m;
            break;
        }
        else if(j<=n)minm = min(minm,a[j] - a[i-1]);
    }
    for (int i = 1; i <= n; i++)
    {
        int j = upper_bound(a + i, a + n+1, a[i-1] + minm) - a;
        if(a[j-1]==a[i-1]+minm)printf("%d-%d\n", i, j-1);
    }
    return 0;
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容