选择客栈

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 724 字

同色调合规咖啡店计数

一本通
练习

正文

// 原题：https://oj.yecheng.tv/p/T1546
// 题意：n 家客栈(色调+最低消费)、能接受最高消费 p；统计同色调且两人间存在消费<=p咖啡店的住宿方案数。
// 思路：逐家扫描，维护每种色调已出现位置与最近一个消费<=p的位置；以当前店为右端，统计左侧同色调且索引<=最近合规点的店数。
// 复杂度：O(n log n) 时间 / O(n) 空间
// 易错点：咖啡店可含端点；左侧店索引必须<=全局最近合规位置才合法。
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,k,p;
    if(!(cin>>n>>k>>p))return 0;
    vector<vector<int>> pos(k);
    long long ans=0;
    vector<int> lastOK(k,-1);
    for(int i=0;i<n;i++){
        int color,cost;cin>>color>>cost;
        if(cost<=p)lastOK[color]=i;
        int cnt=upper_bound(pos[color].begin(),pos[color].end(),lastOK[color])-pos[color].begin();
        ans+=(long long)cnt;
        pos[color].push_back(i);
    }
    cout<<ans<<"\n";
    return 0;
}

选择客栈

正文

一本通·提高篇的其它内容