「NOIP模拟赛by wulala」公主的游戏
wulala：不就一傻逼贪心吗……
就是把公主的wulala的牌都排序一下然后贪心。。。
我只排序wulala的牌，然后把公主的牌放进平衡树T T
每次找后继
不过有了set这样并不会比正解难写，反倒是更为直接2333
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include<iostream> #include<cstdio> #include<cstring> #include<set> #include<map> #include<algorithm> #define inf 1000000000 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,ans; set<int> b; map<int,int> mp; struct data{int v,num;}a[100005]; bool operator<(data a,data b) { return a.v<b.v; } int main() { //freopen("game.in","r",stdin); //freopen("game.out","w",stdout); n=read(); for(int i=1;i<=n;i++) { int x=read(); mp[x]++; if(mp[x]==1)b.insert(x); } m=read(); for(int i=1;i<=m;i++) { a[i].num=read(); a[i].v=read(); } sort(a+1,a+m+1); b.insert(inf); for(int i=1;i<=m;i++) while(a[i].num--) { set<int>::iterator t=b.lower_bound(a[i].v); if(a[i].v==*t)t++; if(*t==inf)break; else { ans++; mp[*t]--; if(!mp[*t])b.erase(*t); } } printf("%d",ans); return 0; } |
计数器 9934686
OI 课件=>
OI 课件=>
不理解为什么"if(a
.v==*t)t++;"，是lower_bound左闭右开吗
是