題意:
? ? ? 兩個(gè)人有一些圖片,矩形的,問(wèn)a最多能夠覆蓋b多少?gòu)垐D片..


思路:

? ? ? 明顯是貪心,但是有一點(diǎn)很疑惑,如果以別人為主,每次都用自己最小的切能覆蓋敵人的方法就wa,而以自己為主,去覆蓋自己可能覆蓋的最大就ac了,證明不了,總感覺(jué)這東西在孫子兵法里會(huì)有,,解題過(guò)程就是先吧兩個(gè)人的所有卡片放一起以 長(zhǎng) 小的在前面,如果 長(zhǎng) 相等 id 大的(被覆蓋那個(gè))在前面排序,保證每一個(gè)卡片能覆蓋的一定在自己的前面,然后從1開(kāi)始跑循環(huán),如果當(dāng)前的點(diǎn)是被覆蓋的點(diǎn),那么直接把他的y扔進(jìn)set里,否則就從set里取出一個(gè)自己能覆蓋的最大的那個(gè)卡片,這樣遍歷到最后就行了,我忘記了題目中的y可能不可能重復(fù)了,如果可以重復(fù)的話直接把set改成muitiset就行了...

#include<stdio.h> #include<algorithm> #include<map> #include<set>#define N_max 220000 #define inf 2000000000 using namespace std;typedef struct {int h ,w ,key; }CARD;CARD card[N_max];bool camp(CARD x ,CARD y) {return x.h < y.h || x.h == y.h && x.w < y.w || x.h == y.h && x.w == y.w && x.key < y.key; }int main () {int t ,i ,n ,sum;scanf("%d" ,&t);while(t--){scanf("%d" ,&n);for(i = 1 ;i <= n ;i ++){scanf("%d %d" ,&card[i].h ,&card[i].w);card[i].key = 1;}for(i = 1 ;i <= n ;i ++){scanf("%d %d" ,&card[i + n].h ,&card[i + n].w);card[i + n].key = 0;}map<int ,int >mark;set<int>st;sort(card + 1 ,card + n + n + 1 ,camp);sum = 0;st.insert(inf);for(n *= 2 ,i = 1 ;i <= n ;i ++){if(card[i].key){int now = *st.lower_bound(-card[i].w);if(now == inf) continue; sum ++;mark[now] --;if(!mark[now])st.erase(now);}else{st.insert(-card[i].w);mark[-card[i].w] ++;}}printf("%d\n" ,sum);}return 0; }

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的hdu4268贪心的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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