a300. NOIP2011 Day1.2.选择客栈 -- NOIP2011提高组Day1第二题 | From: [36.231.161.245] | 發表日期 : 2024-03-02 21:39

#include <bits/stdc++.h>

#define ll long long

using namespace std;

 

int main()

{

    ll n,k,p,a,b;  cin >> n >> k >> p;

    vector<pair<ll,ll>> coffee(k,{0,0});

    vector<int> v[k], okprice;

    for (int i=0; i<n; i++){

        cin >> a >> b;

        if (b<=p)  {coffee[a].first++;  okprice.push_back(i);}

        else       {coffee[a].second++;  v[a].push_back(i);}

    }

    

    // 本身符合 

    ll total=0;

    for (int i=0; i<k; i++){

        ll ac=coffee[i].first, all=coffee[i].second;

        total += ac*all + ac*(ac-1)/2;

    }

    

    // 中間符合 

    for (int i=0; i<k; i++){

    if (v[i].size()<2)  continue;

   

    for (auto station : okprice){

    auto it = upper_bound(v[i].begin(),v[i].end(),station);

    if (it == v[i].end() || it == v[i].begin())  continue;

    ll left = it-v[i].begin();

    ll right= v[i].size() - left;

    total += left*right;

}

}

    

    cout << total << '\n';

 

    return 0;

}

想法:

1. 找本身符合價格的店跟其他店的"組合"

色系x中:  ac為符合價格，all為不符合價格 => total += ac*all + ac*(ac-1)/2

 

2. 找兩個"不符合"價格的店之間是否有符合條件的店