鏈接：https://ac.nowcoder.com/acm/contest/322/M
來源：牛客網(wǎng)

題目描述
HJ養(yǎng)了很多花（99999999999999999999999999999999999盆），并且喜歡把它們排成一排，編號(hào)0~99999999999999999999999999999999998,每天HJ都會(huì)給他的花澆水，但是他很奇怪，他會(huì)澆n(1 <= n <= 2 * 105)次水，每次都會(huì)選擇一個(gè)區(qū)間[l, r]，(0 <= l <= r <= 106),表示對(duì)區(qū)間[l, r]的花都澆一次水。現(xiàn)在問你，通過這些操作之后，被澆了i(1 <= i <= n)次水的花的盆數(shù)。

輸入描述:
輸入：第一行一個(gè)n，表示HJ的操作次數(shù)，接下來的n行，表示每一次選擇的澆水區(qū)間。
輸出描述:
輸出：輸出n個(gè)數(shù)字Cnt1, Cnt2……Cntn,（用空格隔開）Cnti表示被澆了i次水的花的盆數(shù)。
示例1
輸入
復(fù)制
3
0 3
1 3
3 8
輸出
復(fù)制
6 2 1
示例2
輸入
復(fù)制
3
1 3
2 4
5 7
輸出
復(fù)制
5 2 0
說明
對(duì)于樣例1的圖形解釋

被澆了1次的有:0, 4, 5, 6, 7, 8, cnt1 = 6

被澆了2次的有：1, 2. cnt2 = 2

被澆了3次的有: 3 . cnt3 = 3

典型的約束差分題,我做的兩次差分題目全是在牛客網(wǎng)上的.
這種題目的關(guān)鍵是要知道還原.
代碼如下:

#include<bits/stdc++.h> #define ll long long #define inf 0x3f3f3f3f using namespace std;const int maxx=2e6+100; int vis[maxx]; int cnt[maxx]; int n;int main() {cin>>n;ll maxn=-1;ll minn=inf;memset(cnt,0,sizeof(cnt));ll l,r;for(int i=0;i<n;i++){cin>>l>>r;vis[l]++;vis[r+1]--;maxn=max(maxn,r);minn=min(minn,l);}for(int i=minn;i<=maxn;i++){vis[i]+=vis[i-1];//還原,現(xiàn)在的VIS就代表每個(gè)點(diǎn)的被澆水的次數(shù)..}for(int i=minn;i<=maxn;i++){cnt[vis[i]]++;}for(int i=1;i<=n;i++){cout<<cnt[i]<<" ";} }

努力加油a啊,(^o)/~

總結(jié)

以上是生活随笔為你收集整理的HJ浇花(牛客竞赛 约束差分)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。