Hướng dẫn giải của Bedao Mini Contest 26 - Bán sách

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tạo ~1~ cạnh có hướng từ ~i~ đến ~j~ nếu người ~i~ gây ảnh hưởng lên người ~j~ được. Từ đó số lượng sách ít nhất cần phải cho là số lượng đỉnh ~u~ có ~deg_{in}u=0~. Độ phức tạp ~O(N^2)~. Để cái tiến ta sẽ dùng stack. Ta sort những người trong thành phố theo tọa độ của ~x_i~ tăng dần. Sau đó duyệt tăng dần theo tọa độ ~x_i~ và dùng stack để lưu lại những người chưa bị ảnh hưởng bởi người nào hết. Duyệt lại ~1~ lần nữa cho chiều giảm dần của ~x_i~. Độ phức tạp ~O(N)~.

#include<bits/stdc++.h>
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxn=5e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll n;
struct qq
{
    ll x,e;
    bool operator<(const qq&o)
    {
        if(x==o.x) return e<o.e;
        return x<o.x;
    }
}a[maxn];
deque<pli>dq;
vector<ll>g[maxn];
ll deg[maxn];
void solve()
{
    cin >> n ;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i].x >> a[i].e;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
    {
        // xi-xj>=ei-ej -> xi-ei>=xj-ej
        while(dq.size()>0&&dq.back().se>=a[i].x-a[i].e)
        {
            g[i].pb(dq.back().fi);
            deg[dq.back().fi]++;
            dq.pop_back();
        }
        dq.pb({i,a[i].x-a[i].e});
    }
    dq.clear();
    for(int i=n;i>=1;i--)
    {
        if(i<=n&&a[i].x==a[i+1].x&&a[i].e==a[i+1].e) continue;
        while(dq.size()>0&&dq.back().se<=a[i].x+a[i].e)
        {
            g[i].pb(dq.back().fi);
            deg[dq.back().fi]++;
            dq.pop_back();
        }
        dq.pb({i,a[i].x+a[i].e});
    }
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        if(deg[i]==0) ans++;
    }
    cout << ans;
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Bình luận

Hãy đọc nội quy trước khi bình luận.

1

Thien2009 đã bình luận lúc 22, Tháng 6, 2026, 2:42

có một số nhận xét nhỏ mà lúc làm bài mình không nhận ra, mình xin phép được chia sẻ lại ạ

nếu không có nhận xét này thì vẫn có thể giải được bài theo phương pháp có trong tag, chỉ là hơi vất vả hơn

Giả sử đã sắp xếp theo thứ tự tăng dần của $x$, khi đó:

~i<j<k \Rightarrow x_i\le x_j\le x_k~

Xét trường hợp:

~i\rightarrow j~

Ta có:

~|x_i-x_j|\le e_i-e_j~

Vì:

~x_i\le x_j~

nên:

~|x_i-x_j|=x_j-x_i~

Suy ra:

~x_j-x_i\le e_i-e_j~

hay:

~x_j+e_j\le x_i+e_i~

Tương tự với:

~j\rightarrow k~

Ta có:

~|x_j-x_k|\le e_j-e_k~

Vì:

~x_j\le x_k~

nên:

~|x_j-x_k|=x_k-x_j~

Suy ra:

~x_k-x_j\le e_j-e_k~

hay:

~x_k+e_k\le x_j+e_j~

Kết hợp:

~x_k+e_k\le x_j+e_j\le x_i+e_i~

suy ra:

~x_k+e_k\le x_i+e_i~

hay:

~x_k-x_i\le e_i-e_k~

Vì:

~x_i\le x_k~

nên:

~|x_i-x_k|=x_k-x_i~

Do đó:

~|x_i-x_k|\le e_i-e_k~

Suy ra:

~i\rightarrow k~

Vậy:

~i\rightarrow j,\ j\rightarrow k\Rightarrow i\rightarrow k~

Chiều ngược lại:

Giả sử:

~k\rightarrow j,\ j\rightarrow i~

Ta có:

~|x_k-x_j|\le e_k-e_j~

Vì:

~x_j\le x_k~

nên:

~x_k-x_j\le e_k-e_j~

và:

~|x_j-x_i|\le e_j-e_i~

Vì:

~x_i\le x_j~

nên:

~x_j-x_i\le e_j-e_i~

Cộng hai bất đẳng thức:

~x_k-x_i\le e_k-e_i~

Mà:

~|x_k-x_i|=x_k-x_i~

nên:

~|x_k-x_i|\le e_k-e_i~

Suy ra:

~k\rightarrow i~

12

dex111222333444555 đã bình luận lúc 4, Tháng 4, 2025, 9:41

Độ phức tạp O(NlogN) chứ sort tốn O(NlogN) mà