摘要
Title: A1044 Shopping in Mars (25)
Tag: 双指针、二分、前缀和
Memory Limit: 64 MB
Time Limit: 1000 ms

A1044 Shopping in Mars (25)

题意

Shopping in Mars is quite a different experience. The Mars people pay by chained diamonds. Each diamond has a value (in Mars dollars M$). When making the payment, the chain can be cut at any position for only once and some of the diamonds are taken off the chain one by one. Once a diamond is off the chain, it cannot be taken back. For example, if we have a chain of 8 diamonds with values M$3, 2, 1, 5, 4, 6, 8, 7, and we must pay M$15. We may have 3 options:
Cut the chain between 4 and 6, and take off the diamonds from the position 1 to 5 (with values 3+2+1+5+4=15).
Cut before 5 or after 6, and take off the diamonds from the position 4 to 6 (with values 5+4+6=15).
Cut before 8, and take off the diamonds from the position 7 to 8 (with values 8+7=15).
Now given the chain of diamond values and the amount that a customer has to pay, you are supposed to list all the paying options for the customer.
If it is impossible to pay the exact amount, you must suggest solutions with minimum lost.
思路
- 二分+前缀和
  最开始想的做法，也是我最熟悉的做法，但不是最优解，会比双指针多个logn
  先做前缀和，由于数都是正数，故保证是严格递增，所以一定不会有重复的数，所以固定右端点，二分左端点即可，我的代码是找小于等于m的最大值，当然另一种二分方法也可以
  如果二分不出来符合条件的m，那也是二分到了满足条件的区间最右端，就归为另一种情况了
- 双指针
  同理

代码

二分

/*
* @Author: NEFU AB-IN
* @Date: 2023-01-12 22:03:33
* @FilePath: \GPLT\A1044\A1044.cpp
* @LastEditTime: 2023-01-12 22:23:26
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

int n, m;
int a[N];

struct sa
{
    int n, l, r;
};

bool check(int l, int r)
{
    return a[r] - a[l - 1] >= m;
}

signed main()
{
    IOS;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        a[i] += a[i - 1];
    }

    vector<PII> ans;
    vector<sa> tmp;
    // 枚举右端点
    for (int i = 1; i <= n; ++i)
    {
        // 二分左端点
        int l = 1, r = i;
        while (l < r)
        {
            int mid = (l + r + 1) >> 1;
            if (check(mid, i))
                l = mid;
            else
                r = mid - 1;
        }
        if (a[i] - a[l - 1] == m)
            ans.push_back({l, i});
        else
            tmp.push_back({a[i] - a[l - 1], l, i});
    }

    if (SZ(ans))
    {
        sort(ans.begin(), ans.end());
        for (auto &[l, r] : ans)
            cout << l << "-" << r << '\n';
    }
    else
    {
        sort(tmp.begin(), tmp.end(), [&](const sa a, const sa b) {
            if (a.n != b.n)
                return a.n < b.n;
            else
                return a.l < b.l;
        });
        int cnt = 0;
        for (auto &[sum, l, r] : tmp)
        {
            if (sum <= m)
                continue;
            if (!cnt)
                cnt = sum;
            if (cnt == sum)
                cout << l << "-" << r << '\n';
            else
                return 0;
        }
    }
    return 0;
}

双指针

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010, INF = 1e9;

int n, m;
int s[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &s[i]);
        s[i] += s[i - 1];
    }

    int res = INF;
    for (int i = 1, j = 0; i <= n; i ++ )
    {
        while (s[i] - s[j + 1] >= m) j ++ ;
        if (s[i] - s[j] >= m) res = min(res, s[i] - s[j]);
    }

    for (int i = 1, j = 0; i <= n; i ++ )
    {
        while (s[i] - s[j + 1] >= m) j ++ ;
        if (s[i] - s[j] == res) printf("%d-%d\n", j + 1, i);
    }

    return 0;
}

A1044 Shopping in Mars (25)

题意

思路

代码