超绝简单方法👀️

#include<stdio.h>
int main(){
	long long n,k,h=0,xh=0;
	scanf("%lld%lld",&n,&k);
	long long e[n*2+1];
	for(int i=1;i<=n*2;i++){
		scanf("%lld",&e[i]);
	}
    for(int i=1;i<=k-1;i++){
        h=h+e[n*2-i+1]-e[i];
    }
    for(int y=k;y<=n*2-k+1;y=y+2){
        xh=xh+e[y+1]-e[y];
    }
    printf("%lld",xh+h);
	return 0;
}

根据题意可以知道是所有离开的时间减去进入的时间，因此只需要标记离开和进入，然后减去进入时间加上离开时间就行

#include<iostream>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
const ll N=1e7;
ll a[N],b[N];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n,num=0,k;
    cin>>n>>k;
    for(int i=1;i<=2*n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=2*n;i++){
        if(i<=k){
            b[i]=1;
        }else if(i>2*n-k){
            b[i]=0;
        }else{
            b[i]=num%2;
            num++;
        }
    }
    int sum=0;
    for(int i=1;i<=2*n;i++){
        if(b[i]==1){
            sum-=a[i];
        }else{
            sum+=a[i];
        }
    }
    cout<<sum<<"\n";
    return 0;
}

要解决这个问题，我们需要找到一种方法，将传感器记录的时间点配对为进入时间和离开时间，使得在满足“同时在超市的人数不超过 k ”的约束下，所有人的总停留时间最大。

问题分析

传感器记录了 2n 个时间点（ a_1 < a_2 < \dots < a_{2n} ），每个时间点对应一次“进入”或“离开”操作，但具体类型未知。我们的目标是合理配对这些时间点，使得：

• 每个进入时间对应一个离开时间（进入时间 < 离开时间）；
• 任意时刻同时在超市的人数不超过 k ；
• 所有配对的“离开时间 - 进入时间”之和最大。

关键思路：贪心 + 栈模拟

为了最大化总停留时间，我们需要让尽可能多的人在超市内停留尽可能长的时间，同时满足人数限制 k 。具体策略如下：

1. 前 k 个时间点标记为“进入”：因为要先让 k 个人进入，才能开始计时。
2. 后 k 个时间点标记为“离开”：因为要让最后 k 个人尽可能晚离开，以延长停留时间。
3. 中间时间点交替标记：对于中间的时间点，交替标记为“进入”和“离开”，保证人数不超过 k 。
4. 栈模拟配对：用栈存储“进入时间”，遇到“离开时间”时，弹出栈顶的“进入时间”，计算停留时间并累加。

代码解析

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

void yy()
{
    int n;
    cin >> n;
    int a[2 * n + 5];
    int b[2 * n + 5]; // 标记是否为进入时间，1表示进入，0表示离开
    int cnt = 0;
    int k;
    cin >> k;
    // 读取所有时间点
    for (int i = 1; i <= 2 * n; i++)
    {
        cin >> a[i];
    }
    // 组标记前k个为进入，后k个为离开，中间交替
    for (int i = 1; i <= 2 * n; i++)
    {
        if (i <= k)
        {
            b[i] = 1; // 前k个是进入
        }
        else if (i > 2 * n - k)
        {
            b[i] = 0; // 后k个是离开
        }
        else
        {
            b[i] = cnt % 2; // 中间交替
            cnt++;
        }
    }
    stack<int> st;
    int ans = 0;
    for (int i = 1; i <= 2 * n; i++)
    {
        if (b[i])
        {
            st.push(a[i]); // 进入时间入栈
        }
        else
        {
            ans += a[i] - st.top(); // 计算停留时间并累加
            st.pop();
        }
    }
    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        yy();
    return 0;
}

复杂度分析

• 时间复杂度： O(n) ，其中 n 是输入的时间点对数（ 2n 个时间点）。读取时间点、标记进入/离开、栈模拟配对的操作均为线性时间。
• 空间复杂度： O(n) ，主要用于存储时间点数组和栈的空间。

该方法通过贪心策略合理配对进入和离开时间，确保在人数限制下总停留时间最大，是解决该问题的高效方案。