编程知识 购物 网址 新闻 笑话 | 软件 日历 阅读 图书馆 China
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
vbs/VBScript DOS/BAT hta htc python perl 游戏相关 VBA 远程脚本 ColdFusion ruby专题 autoit seraphzone PowerShell linux shell Lua Golang Erlang 其它教程 CSS/HTML/Xhtml html5 CSS XML/XSLT Dreamweaver教程 经验交流
站长资讯 .NET新手 ASP.NET C# WinForm Silverlight WCF CLR WPF XNA VisualStudio ASP.NET-MVC .NET控件开发 EntityFramework WinRT-Metro Java C++ PHP Delphi Python Ruby C语言 Erlang Go Swift Scala R语言 Verilog 其它语言 架构设计 面向对象 设计模式 领域驱动 Html-Css JavaScript jQuery HTML5 SharePoint GIS技术 SAP OracleERP DynamicsCRM K2 BPM 信息安全 企业信息 Android开发 iOS开发 WindowsPhone WindowsMobile 其他手机 敏捷开发 项目管理 软件工程 SQLServer Oracle MySQL NoSQL 其它数据库 Windows7 WindowsServer Linux
   -> C++ -> P2286 [HNOI2004]宠物收养场 -> 正文阅读

[C++]P2286 [HNOI2004]宠物收养场

P2286 [HNOI2004]宠物收养场 题目描述
凡凡开了一间宠物收养场。收养场提供两种服务:收养被主人遗弃的宠物和让新的主人领养这些宠物。
每个领养者都希望领养到自己满意的宠物,凡凡根据领养者的要求通过他自己发明的一个特殊的公式,得出该领养者希望领养的宠物的特点值a(a是一个正整数,a<2^31),而他也给每个处在收养场的宠物一个特点值。这样他就能够很方便的处理整个领养宠物的过程了,宠物收养场总是会有两种情况发生:被遗弃的宠物过多或者是想要收养宠物的人太多,而宠物太少。
被遗弃的宠物过多时,假若到来一个领养者,这个领养者希望领养的宠物的特点值为a,那么它将会领养一只目前未被领养的宠物中特点值最接近a的一只宠物。(任何两只宠物的特点值都不可能是相同的,任何两个领养者的希望领养宠物的特点值也不可能是一样的)如果有两只满足要求的宠物,即存在两只宠物他们的特点值分别为a-b和a+b,那么领养者将会领养特点值为a-b的那只宠物。
收养宠物的人过多,假若到来一只被收养的宠物,那么哪个领养者能够领养它呢?能够领养它的领养者,是那个希望被领养宠物的特点值最接近该宠物特点值的领养者,如果该宠物的特点值为a,存在两个领养者他们希望领养宠物的特点值分别为a-b和a+b,那么特点值为a-b的那个领养者将成功领养该宠物。
一个领养者领养了一个特点值为a的宠物,而它本身希望领养的宠物的特点值为b,那么这个领养者的不满意程度为abs(a-b)。
你得到了一年当中,领养者和被收养宠物到来收养所的情况,请你计算所有收养了宠物的领养者的不满意程度的总和。这一年初始时,收养所里面既没有宠物,也没有领养者。
输入输出格式
输入格式:
第一行为一个正整数n,n<=80000,表示一年当中来到收养场的宠物和领养者的总数。接下来的n行,按到来时间的先后顺序描述了一年当中来到收养场的宠物和领养者的情况。每行有两个正整数a, b,其中a=0表示宠物,a=1表示领养者,b表示宠物的特点值或是领养者希望领养宠物的特点值。(同一时间呆在收养所中的,要么全是宠物,要么全是领养者,这些宠物和领养者的个数不会超过10000个)
输出格式:
仅有一个正整数,表示一年当中所有收养了宠物的领养者的不满意程度的总和mod 1000000以后的结果。
输入输出样例
输入样例#1: 复制

5                  
0 2                      
0 4                         
1 3
1 2
1 5

输出样例#1: 复制

3
注:abs(3-2) + abs(2-4)=3,
最后一个领养者没有宠物可以领养。

code

  1 #include<cstdio>
  2 #include<algorithm>
  3 using namespace std;
  4 
  5 const int N = 100100;
  6 const int mod = 1000000;
  7 
  8 int ch[N][2],fa[N],siz[N],data[N];
  9 int Root,tn;
 10 
 11 inline char nc() {
 12     static char buf[100000],*p1 = buf,*p2 = buf;
 13     return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2) ? EOF : *p1++;
 14 }
 15 inline int read() {
 16     int x = 0,f = 1;char ch = nc();
 17     for (; ch<'0'||ch>'9'; ch = nc())
 18         if (ch=='-') f = -1;
 19     for (; ch>='0'&&ch<='9'; ch = nc())
 20         x = x*10+ch-'0';
 21     return x * f;
 22 }
 23 inline int son(int x) {
 24     return x == ch[fa[x]][1];
 25 }
 26 inline void pushup(int x) {
 27     siz[x] = siz[ch[x][1]] + siz[ch[x][0]] + 1;
 28 }
 29 inline void rotate(int x) {
 30     int y = fa[x],z = fa[y],b = son(x),c = son(y),a = ch[x][!b];
 31     if (z) ch[z][c] = x;else Root = x;fa[x] = z;
 32     ch[x][!b] = y;fa[y] = x;
 33     ch[y][b] = a;if (a) fa[a] = y;
 34     pushup(y);pushup(x);
 35 }
 36 inline void splay(int x,int rt) {
 37     while (fa[x] != rt) {
 38         int y = fa[x],z = fa[y];
 39         if (z==rt) rotate(x);
 40         else {
 41             if (son(x) == son(y)) rotate(y),rotate(x);
 42             else rotate(x),rotate(x);
 43         }
 44     }
 45 }
 46 inline int getpre(int x) {
 47     int p = Root,ans; 
 48     while (p) {
 49         if (x <= data[p]) p = ch[p][0];
 50         else ans = p,p = ch[p][1];
 51     }
 52     return ans;
 53 }
 54 inline int getsuc(int x) {
 55     int p = Root,ans;
 56     while (p) {
 57         if (x >= data[p]) p = ch[p][1];
 58         else ans = p,p = ch[p][0];
 59     }
 60     return ans;
 61 }
 62 inline int getk(int k) {
 63     int p = Root,ans = 0;
 64     while (true) {
 65         if (k < data[p]) p = ch[p][0];
 66         else {
 67             ans += (ch[p][0] ? siz[ch[p][0]] : 0);
 68             if (k == data[p]) {
 69                 splay(p,0);return ans + 1;
 70             }
 71             ans ++;
 72             p = ch[p][1];
 73         }
 74     }
 75 }
 76 inline int getkth(int k) {
 77     int p = Root;
 78     while (true) {
 79         if (k == siz[ch[p][0]]+1) return p;
 80         if (ch[p][0] && k <= siz[ch[p][0]]) p = ch[p][0];
 81         else {
 82             k -= ((ch[p][0] ? siz[ch[p][0]] : 0) + 1);
 83             p = ch[p][1];
 84         }
 85     }
 86 }
 87 inline void Insert(int x) {
 88     if (Root==0) {
 89         ++tn;Root = tn;
 90         ch[tn][1] = ch[tn][0] = fa[tn] = 0;
 91         siz[tn] = 1;data[tn] = x;
 92         return ;
 93     }
 94     int p = Root,pa = 0;
 95     while (true) {
 96         pa = p;
 97         p = ch[p][x > data[p]];
 98         if (p==0) {
 99             ++tn;
100             ch[tn][1] = ch[tn][0] = 0;fa[tn] = pa;
101             ch[pa][x > data[pa]] = tn;
102             siz[tn] = 1;data[tn] = x;
103             pushup(pa),splay(tn,0);break;
104         }
105     }
106 }
107 inline void Clear(int x) {
108     ch[x][0] = ch[x][1] = fa[x] = siz[x] = data[x] = 0;
109 }
110 inline void Delete(int x) {
111     getk(x);
112     if (!ch[Root][0] && !ch[Root][1]) { Clear(Root);Root = 0;return;}
113     if (!ch[Root][0]) {
114         int tmp = Root;Root = ch[Root][1];fa[Root] = 0;Clear(tmp);return;
115     }
116     else if (!ch[Root][1]) {
117         int tmp = Root;Root = ch[Root][0];fa[Root] = 0;Clear(tmp);return;
118     }
119     int tmp = Root,pre = ch[Root][0];
120     while (ch[pre][1]) pre = ch[pre][1];
121     splay(pre,0);
122     ch[Root][1] = ch[tmp][1];
123     fa[ch[tmp][1]] = Root;
124     Clear(tmp);
125     pushup(Root);
126 }
127 int main() {
128     int n = read(),ans = 0,s;
129     while (n--) {
130         int a = read(),b = read();
131         if (!siz[Root]) {s = a;Insert(b);continue;}
132         if (a==s) {Insert(b);continue;}
133         int p1 = getpre(b),p2 = getsuc(b);
134         int k1 = data[p1],k2 = data[p2];
135         if (k1 && k2) {
136             if (abs(k1-b) <= abs(k2-b)) 
137                 ans += abs(k1-b),ans = ans%mod,Delete(k1);
138             else ans += abs(k2-b),ans = ans%mod,Delete(k2);
139         }
140         else if (k1) ans += abs(k1-b),ans = ans%mod,Delete(k1);
141         else if (k2) ans += abs(k2-b),ans = ans%mod,Delete(k2);
142     }
143     ans = ans%mod;
144     printf("%d",ans);
145     return 0;
146 }

 来一发set
只是略慢,实测set在开O2的情况下 与 splay不开O2的情况下差不多。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<set>
 4 #include<algorithm>
 5 
 6 const int mod = 1000000;
 7 using namespace std;
 8 
 9 
10 inline char nc() {
11     static char buf[100000],*p1 = buf,*p2 = buf;
12     return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2) ? EOF : *p1++;
13 }
14 inline int read() {
15     int x = 0,f = 1;char ch = nc();
16     for (; ch<'0'||ch>'9'; ch = nc()) 
17         if (ch=='-') f = -1;
18     for (; ch>='0'&&ch<='9'; ch = nc()) 
19         x = x*10+ch-'0';
20     return x * f;
21 }
22 
23 set<int> s;
24 set<int>::iterator it;
25 
26 int main()
27 {
28     int n = read(),sta,ans = 0;
29     while (n--) {
30         int a = read(),b = read(),k1,k2,t1 = 1,t2 = 1;
31         if (s.empty()) {s.insert(b);sta = a;continue;}
32         if (a == sta) {s.insert(b);continue;}
33         it = s.lower_bound(b);
34         k2 = *it;
35         if (it==s.end()) t2 = 0; // 左闭右开
36         else if (k2==b) continue;
37         if (it == s.begin()) t1 = 0;
38         else it--,k1 = *it;
39 
40         if (t1 && t2) {
41             if (abs(k1-b) <= abs(k2-b)) 
42                 ans += abs(k1-b),ans = ans%mod,s.erase(k1);
43             else ans += abs(k2-b),ans = ans%mod,s.erase(k2);
44         }
45         else if (t1) ans += abs(k1-b),ans = ans%mod,s.erase(k1);
46         else if (t2) ans += abs(k2-b),ans = ans%mod,s.erase(k2);
47     }
48     ans = ans % mod;
49     printf("%d",ans);
50     return 0;
51 }

  C++ 最新文章
关于poin与references
019:别叫,这个大整数已经很简化了!
c++智能指针详解
BZOJ1269: [AHOI2006]文本编辑器editor
洛谷P3835 【模板】可持久化平衡树
洛谷P2925 [USACO08DEC]干草出售Hay For Sa
POJ 2987 Firing
树的重心
第一章 作业7.
【左神算法课】超经典:求两单向链表交点(
上一篇文章      下一篇文章      查看所有文章
加:2017-12-05 23:23:29  更:2017-12-05 23:23:42 
 
360图书馆 软件开发资料 购物精选 新闻资讯 Chinese Culture 三丰软件 开发 中国文化 阅读网 日历 万年历 2019年9日历
2019-9-16 19:15:37
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  编程知识