C题解 | #小Why的商品归位#
小Why的商品归位
https://ac.nowcoder.com/acm/contest/64384/C
C题解 | #小Why的商品归位#
我们可以这样想，对于一个商品假设一开始在1，然后要去4
那么他在1-3这个区间就一定会占据一个购物车位置，因为在这期间不可能将它放下来
这样就可以直接通过差分来维护在商品的“占据情况”
然后找到最多商品同时占据的点，然后除以k向上取整就是答案了
代码如下
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int n,m,k,cha[N];
void solve()
{
cin >> n >> m >> k;
for(int i = 1; i <= m; i++)
{
int l,r;
cin >> l >> r;
cha[l]++,cha[r]--;
}
int res = 0;
for(int i = 1; i <= n; i++)
{
cha[i] += cha[i - 1];
res = max(res,cha[i]);
}
cout << (res - 1)/k + 1 << '\n';
}
int main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t = 1;
while(t--) solve();
return 0;
}
查看11道真题和解析
