題目描述

巧克力王國里的巧克力都是由牛奶和可可做成的。但是并不是每一塊巧克力都受王國人民的歡迎，因?yàn)榇蠹叶疾幌矚g過于甜的巧克力。對(duì)于每一塊巧克力，我們?cè)O(shè)x和y為其牛奶和可可的含量。由于每個(gè)人對(duì)于甜的程度都有自己的評(píng)判標(biāo)準(zhǔn)，所以每個(gè)人都有兩個(gè)參數(shù)a和b，分別為他自己為牛奶和可可定義的權(quán)重，因此牛奶和可可含量分別為x和y的巧克力對(duì)于他的甜味程度即為ax + by。而每個(gè)人又有一個(gè)甜味限度c，所有甜味程度大于等于c的巧克力他都無法接受。每塊巧克力都有一個(gè)美味值h。現(xiàn)在我們想知道對(duì)于每個(gè)人，他所能接受的巧克力的美味值之和為多少

輸入

第一行兩個(gè)正整數(shù)n和m，分別表示巧克力個(gè)數(shù)和詢問個(gè)數(shù)。接下來n行，每行三個(gè)整數(shù)x,y,h，含義如題目所示。再接下來m行，每行三個(gè)整數(shù)a,b,c，含義如題目所示。

輸出

輸出m行，其中第i行表示第i個(gè)人所能接受的巧克力的美味值之和。

樣例輸入

3 3
1 2 5
3 1 4
2 2 1
2 1 6
1 3 5
1 3 7

樣例輸出

5
0
4

---

題解

KD-tree

樸素的n^2暴力顯然會(huì)TLE，我們來優(yōu)化這個(gè)過程。

題目要求出某條直線下方的所有點(diǎn)的權(quán)值和，不過看做直線并沒有什么用。

考慮，如果能夠使得某一些點(diǎn)都符合條件或都不符合條件，那么就可以降低查找的時(shí)間。

所以我們使用KD-tree來維護(hù)平面上的點(diǎn)。查詢時(shí)，判斷一下區(qū)域內(nèi)的點(diǎn)是否都滿足條件或都不滿足條件，可以減去大量時(shí)間。

不過時(shí)間復(fù)雜度上界貌似還是O(n^2)的

估價(jià)函數(shù)需要分4種情況討論

#include <cstdio> #include <algorithm> #define N 50010 using namespace std; typedef long long ll; struct data {ll p[2] , v , maxn[2] , minn[2] , sum;int c[2]; }a[N]; int d , root; bool cmp(data a , data b) {return a.p[d] == b.p[d] ? a.p[d ^ 1] < b.p[d ^ 1] : a.p[d] < b.p[d]; } void pushup(int k , int x) {a[k].maxn[0] = max(a[k].maxn[0] , a[x].maxn[0]);a[k].maxn[1] = max(a[k].maxn[1] , a[x].maxn[1]);a[k].minn[0] = min(a[k].minn[0] , a[x].minn[0]);a[k].minn[1] = min(a[k].minn[1] , a[x].minn[1]);a[k].sum += a[x].sum; } int build(int l , int r , int now) {int mid = (l + r) >> 1;d = now , nth_element(a + l , a + mid , a + r + 1 , cmp);a[mid].maxn[0] = a[mid].minn[0] = a[mid].p[0];a[mid].maxn[1] = a[mid].minn[1] = a[mid].p[1];a[mid].sum = a[mid].v;if(l < mid) a[mid].c[0] = build(l , mid - 1 , now ^ 1) , pushup(mid , a[mid].c[0]);if(r > mid) a[mid].c[1] = build(mid + 1 , r , now ^ 1) , pushup(mid , a[mid].c[1]);return mid; } int getdis(int k , ll x , ll y , ll z) {if(x >= 0 && y >= 0){if(x * a[k].maxn[0] + y * a[k].maxn[1] < z) return 1;if(x * a[k].minn[0] + y * a[k].minn[1] >= z) return -1;}else if(x < 0 && y >= 0){if(x * a[k].minn[0] + y * a[k].maxn[1] < z) return 1;if(x * a[k].maxn[0] + y * a[k].minn[1] >= z) return -1;}else if(x >= 0 && y < 0){if(x * a[k].maxn[0] + y * a[k].minn[1] < z) return 1;if(x * a[k].minn[0] + y * a[k].maxn[1] >= z) return -1;}else{if(x * a[k].minn[0] + y * a[k].minn[1] < z) return 1;if(x * a[k].maxn[0] + y * a[k].maxn[1] >= z) return -1;}return 0; } ll query(int k , ll x , ll y , ll z) {int t = getdis(k , x , y , z);if(t == 1) return a[k].sum;if(t == -1) return 0;ll ans = 0;if(a[k].p[0] * x + a[k].p[1] * y < z) ans += a[k].v;if(a[k].c[0]) ans += query(a[k].c[0] , x , y , z);if(a[k].c[1]) ans += query(a[k].c[1] , x , y , z);return ans; } int main() {int n , m , i;ll x , y , z;scanf("%d%d" , &n , &m);for(i = 1 ; i <= n ; i ++ ) scanf("%lld%lld%lld" , &a[i].p[0] , &a[i].p[1] , &a[i].v);root = build(1 , n , 0);while(m -- ) scanf("%lld%lld%lld" , &x , &y , &z) , printf("%lld\n" , query(root , x , y , z));return 0; }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/GXZlegend/p/7110220.html

總結(jié)

以上是生活随笔為你收集整理的【bzoj2850】巧克力王国 KD-tree的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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