題意：

有一艘船，船上有 \(n\) 個旗桿，每個旗桿上有 \(h_i\) 個小節(jié)。每根旗桿上會掛 \(k_i\) 張帆

每個小節(jié)最多掛一個帆。在風中，帆的不同排布方式會產(chǎn)生不同的推動力

對于任意一張帆，他的推動力折扣等于再它后面并且和它在同一高度的帆的數(shù)目

所有帆的任意一種位置組合的推動力折扣和等于在該位置下所有帆的推動力折扣的和

求所有位置組合最小的推動力折扣和

顯然有一種貪心方案：

設每個位置上的旗子數(shù)量為 \(s_i\)，那么按照旗桿長度從小到大排序

每次貪心的找到可行的位置中，旗子數(shù)量最少的 \(k\) 個放旗子即可（即 \(s_i+1\))

最后 \(\sum\limits_{i}\frac{s_i(s_i-1)}{2}\) 就是答案了。

時間復雜度 \(O(\sum\limits_{i=1}^nh_i)\)

時間復雜度不行，如何優(yōu)化？

按照 \(s_i\) 維護一個排序后的數(shù)列，相當于每次給區(qū)間加 \(1\)

區(qū)間加 \(1\) 可能使得區(qū)間不再有序！

原來的 \(s_i:~[1,1,1,1,3]\)

\([1,3]\) 加 \(1\) 后的數(shù)列應為： \([1,2,2,2,3]\)

實際上也是區(qū)間加法！我們只要找到之后第一個比之前這個數(shù)大的即可

可以利用線段樹優(yōu)化，時間復雜度 \(O(n~log~n)\)

#include <map> #include <set> #include <ctime> #include <queue> #include <stack> #include <cmath> #include <vector> #include <bitset> #include <cstdio> #include <cctype> #include <string> #include <numeric> #include <cstring> #include <cassert> #include <climits> #include <cstdlib> #include <iostream> #include <algorithm> #include <functional> using namespace std ; #define int long long #define rep(i, a, b) for (int i = (a); i <= (b); i++) #define per(i, a, b) for (int i = (a); i >= (b); i--) #define loop(s, v, it) for (s::iterator it = v.begin(); it != v.end(); it++) #define cont(i, x) for (int i = head[x]; i; i = e[i].nxt) #define clr(a) memset(a, 0, sizeof(a)) #define ass(a, sum) memset(a, sum, sizeof(a)) #define lowbit(x) (x & -x) #define all(x) x.begin(), x.end() #define ub upper_bound #define lb lower_bound #define pq priority_queue #define mp make_pair #define pb push_back #define fi first #define se second #define iv inline void #define enter cout << endl #define siz(x) ((int)x.size()) #define file(x) freopen(#x".in", "r", stdin),freopen(#x".out", "w", stdout) typedef long long ll ; typedef unsigned long long ull ; typedef pair <int, int> pii ; typedef vector <int> vi ; typedef vector <pii> vii ; typedef queue <int> qi ; typedef queue <pii> qii ; typedef set <int> si ; typedef map <int, int> mii ; typedef map <string, int> msi ; const int N = 100010 ; const int INF = 0x3f3f3f3f ; const int iinf = 1 << 30 ; const ll linf = 2e18 ; const int MOD = 1000000007 ; const double eps = 1e-7 ; void print(int x) { cout << x << endl ; exit(0) ; } void PRINT(string x) { cout << x << endl ; exit(0) ; } void douout(double x){ printf("%lf\n", x + 0.0000000001) ; }int n, m ;struct node {int h, s ; } a[N] ;bool cmp(node a, node b) {return a.h < b.h ; }struct Seg {int l, r, mn, mx, tag ;#define ls(x) x << 1#define rs(x) x << 1 | 1#define l(x) tr[x].l#define r(x) tr[x].r#define tag(x) tr[x].tag#define mn(x) tr[x].mn#define mx(x) tr[x].mx } tr[N << 2] ;void pushup(int x) {mn(x) = min(mn(ls(x)), mn(rs(x))) ;mx(x) = max(mx(ls(x)), mx(rs(x))) ; }void pushdown(int x) {if (tag(x)) {tag(ls(x)) += tag(x) ;tag(rs(x)) += tag(x) ;mn(ls(x)) += tag(x) ;mn(rs(x)) += tag(x) ;mx(ls(x)) += tag(x) ;mx(rs(x)) += tag(x) ;tag(x) = 0 ;} }void build(int x, int l, int r) {l(x) = l, r(x) = r ;if (l == r) return ;int mid = (l(x) + r(x)) >> 1 ;build(ls(x), l, mid) ;build(rs(x), mid + 1, r) ;pushup(x) ; }void modify(int x, int l, int r) {if (l <= l(x) && r(x) <= r) {tag(x)++ ; mx(x)++ ; mn(x)++ ;return ;}pushdown(x) ;int mid = (l(x) + r(x)) >> 1 ;if (l <= mid) modify(ls(x), l, r) ;if (mid < r) modify(rs(x), l, r) ;pushup(x) ; }int qmid(int x, int c) {if (l(x) == r(x)) return mn(x) ;pushdown(x) ;int mid = (l(x) + r(x)) >> 1 ;if (c <= mid) return qmid(ls(x), c) ;else return qmid(rs(x), c) ; }int ql(int x, int c) {if (l(x) == r(x)) return l(x) ;pushdown(x) ;if (mn(ls(x)) <= c) return ql(ls(x), c) ;else return ql(rs(x), c) ; }int qr(int x, int c) {if (l(x) == r(x)) return l(x) ;pushdown(x) ;if (mx(rs(x)) >= c) return qr(rs(x), c) ;else return qr(ls(x), c) ; }int query(int x) {if (l(x) == r(x)) return mn(x) * (mn(x) - 1) / 2 ;pushdown(x) ;return query(ls(x)) + query(rs(x)) ; }signed main(){scanf("%lld", &n) ;rep(i, 1, n) {scanf("%lld%lld", &a[i].h, &a[i].s) ;m = max(m, a[i].h) ;}sort(a + 1, a + n + 1, cmp) ;build(1, 1, m) ;rep(i, 1, n) {int res = qmid(1, a[i].h - a[i].s + 1) ;int L = ql(1, res), R = qr(1, res) ;if (R < a[i].h) {int len = a[i].h - R ;modify(1, R + 1, a[i].h) ;modify(1, L, L + a[i].s - len - 1) ;} else {modify(1, L, L + a[i].s - 1) ;}}printf("%lld\n", query(1)) ;return 0 ; }/* 寫代碼時請注意：1.ll？數(shù)組大小，邊界？數(shù)據(jù)范圍？2.精度？3.特判？4.至少做一些 思考提醒：1.最大值最小->二分？2.可以貪心么？不行dp可以么3.可以優(yōu)化么4.維護區(qū)間用什么數(shù)據(jù)結構？5.統(tǒng)計方案是用dp？模了么？6.逆向思維？ */

轉載于:https://www.cnblogs.com/harryhqg/p/10451343.html

總結

以上是生活随笔為你收集整理的IOI 2007 Sail (线段树+贪心)的全部內容，希望文章能夠幫你解決所遇到的問題。

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