京东C++ 研发4.18笔试

第一题：

股票亏损最小问题

超时 通过%27case

第二题：

完全没思路，直接return n

通过%22case，后来网上找到是icpc原题，博主题解如下

I. Starting a Scenic Railroad Service

题意：给出n个乘客的乘车区间，问在乘客自主选择座位和统一安排座位的情况下分别最少需要多少个座位。

题意：

n个人，ai上车，bi下车，两种预定方案：1：随便订，但是要选之前没订购过的。2：最优策略，选完位置再安排座位。

问两种方案需要的座位各多少。

思路：

对于第一种，答案是人数最多的区间的人数，因为只要区间有重叠，选票可能会冲突，把最大的冲突给安排了不就行了吗。

对于第二种，只要知道最多同时有多少人在车上就行了。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int ans1,ans2,a[maxn],b[maxn],r[maxn],MAX;
int sc[maxn];
int xc[maxn];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i];
        sc[a[i]]++;//a[i]上车人数
        xc[b[i]]++;//b[i]下车人数
        r[a[i]]++;
        r[b[i]]--;//站点[的人数
        MAX = max(MAX, b[i]);//最远站
    }
    for(int i = 1;i<= MAX;i++)
    {
        sc[i]+= sc[i-1];
        xc[i]+= xc[i-1];
    }
    for(int i=1; i<=n;i++)
        ans1=max(ans1,sc[b[i]-1]-xc[a[i]]);//精华所在啊，求的是在该区间的总人数
    for(int i=1;i<=MAX;i++)
    {
        r[i]+=r[i-1];
        ans2 = max(ans2,r[i]);
    }
    cout<<ans1<<' '<<ans2<<endl;
 
    return 0;
}

————————————————
版权声明：本文为CSDN博主「婷霸」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/Healer66/article/details/82463991