漫长的补结题报告之路 poj3622
2024-10-14 11:19:39
题意（引用）：题意：有很多种草，有两个属性：价格和新鲜度；有很多牛，它们都会各自需求一种草，要求是其价格最低为ai，新鲜度最低为bi，且这些牛不希望自己的草和别人的一样。问要满足所有需求的最小花费是多少？
一开始想的都是各种匹配，结果正解是贪心……
应该来说想不到好方法时，不是二分答案就是贪心了吧？
先按新鲜度为第一关键字，价格为第二关键字排序
从最挑剔（新鲜度要求越高）的牛开始考虑，每次选择应当是价格最小并且能能满足当前牛的牧草
可以这样想：当前处理的牛使没选过的牛中最挑剔的，新鲜度能满足当前牛的一定也能满足之前牛
再来考虑价格，因为价格是最低要求，这次价格选择最低限度的，显然会为之后的选择打开更多空间
所以每次每次选择应当是价格最小并且能能满足当前牛的牧草是最优的
朴素模拟复杂度O(nm) ，所以需要各种数据结构优化
考虑到好久没有写平衡树（其实是一开始想到的就是平衡树）
于是就写了splay
var cv,cw,v,w,d,fa:array[..] of longint;
son:array[..,..] of longint;
root,i,j,p,n,m,t,h:longint;
ans:int64;
function succ(x:longint):longint; //找后继
var p:longint;
begin
p:=son[x,];
while son[p,]<> do p:=son[p,];
exit(p);
end; procedure rotate(x,w:longint);
var y:longint;
begin
y:=fa[x];
if fa[y]<> then
begin
if son[fa[y],]=y then son[fa[y],]:=x
else son[fa[y],]:=x;
end;
fa[x]:=fa[y];
son[y,-w]:=son[x,w];
if son[x,w]<> then fa[son[x,w]]:=y;
son[x,w]:=y;
fa[y]:=x;
end; procedure splay(x:longint); //拍习惯了就快了，还是那句话在哪里就往反向转
var y:longint;
begin
while fa[x]<> do
begin
y:=fa[x];
if fa[y]= then
begin
if son[y,]=x then rotate(x,)
else rotate(x,);
end
else begin
if son[fa[y],]=y then
begin
if son[y,]=x then
begin
rotate(y,);
rotate(x,);
end
else begin
rotate(x,);
rotate(x,);
end;
end
else begin
if son[y,]=x then
begin
rotate(x,);
rotate(x,);
end
else begin
rotate(y,);
rotate(x,);
end;
end;
end;
end;
root:=x;
end; procedure delete(x:longint); //删除写得比较丑陋
var p,y,q,u:longint;
begin
y:=fa[x];
if y= then q:=
else if son[y,]=x then q:=
else if son[y,]=x then q:=;
if (son[x,]<>) and (son[x,]<>) then
begin
p:=succ(x);
if (son[p,]<>) and (fa[p]<>x) then
begin
son[fa[p],]:=son[p,];
fa[son[p,]]:=fa[p];
end
else if fa[p]<>x then son[fa[p],]:=;
son[p,]:=son[x,];
fa[son[x,]]:=p;
if fa[p]<>x then
begin
son[p,]:=son[x,];
fa[son[x,]]:=p;
end;
if y<> then son[y,q]:=p;
fa[p]:=y;
splay(p);
end
else begin
if y<> then
begin
if son[x,]<> then
begin
son[y,q]:=son[x,];
fa[son[x,]]:=y;
end;
if son[x,]<> then
begin
son[y,q]:=son[x,];
fa[son[x,]]:=y;
end;
end;
if son[x,]<> then u:=son[x,] else u:=son[x,];
if y= then
begin
root:=u;
fa[u]:=;
end
else splay(y);
end;
dec(h);
fa[x]:=;
son[x,]:=;
son[x,]:=;
d[x]:=;
end; procedure insert(x:longint);
var p:longint;
begin
inc(t);
inc(h);
d[t]:=x;
if h= then
begin
root:=;
fa[t]:=;
end
else begin
p:=root;
repeat
if d[p]>=x then
begin
if son[p,]= then break;
p:=son[p,];
end
else begin
if son[p,]= then break;
p:=son[p,];
end;
until false;
fa[t]:=p;
if d[p]>=x then son[p,]:=t else son[p,]:=t;
splay(t);
end;
end; procedure swap(var a,b:longint);
var c:longint;
begin
c:=a;
a:=b;
b:=c;
end; procedure sortc(l,r:longint);
var i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=cv[(l+r) shr ];
y:=cw[(l+r) shr ];
repeat
while (cv[i]<x) or ((cv[i]=x) and (cw[i]<y)) do inc(i);
while (x<cv[j]) or ((cv[j]=x) and (cw[j]>y)) do dec(j);
if not(i>j) then
begin
swap(cv[i],cv[j]);
swap(cw[i],cw[j]);
inc(i);
j:=j-;
end;
until i>j;
if l<j then sortc(l,j);
if i<r then sortc(i,r);
end; procedure sort(l,r:longint);
var i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=v[(l+r) shr ];
y:=w[(l+r) shr ];
repeat
while (v[i]<x) or ((v[i]=x) and (w[i]<y)) do inc(i);
while (x<v[j]) or ((v[j]=x) and (w[j]>y)) do dec(j);
if not(i>j) then
begin
swap(w[i],w[j]);
swap(v[i],v[j]);
inc(i);
j:=j-;
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;
begin
readln(n,m);
for i:= to n do
readln(cw[i],cv[i]);
for i:= to m do
readln(w[i],v[i]);
if m<n then
begin
writeln(-);
halt;
end;
sortc(,n);
sort(,m);
j:=m;
t:=;
root:=;
fillchar(son,sizeof(son),);
fillchar(fa,sizeof(fa),);
for i:=n downto do
begin
while v[j]>=cv[i] do
begin
insert(w[j]);
dec(j);
end;
insert(cw[i]);
p:=succ(t);
if p<> then
begin
ans:=ans+d[p];
delete(t);
delete(p);
end
else begin
ans:=-;
break;
end;
end;
writeln(ans);
end.
话说splay终于写对了还是1Y，好高兴
最新文章
- django server之间通过remote user 相互调用
- 思维导图MindManager的文件格式与例图
- Oracle: SQL组合不同字段作为一个查询条件
- Linux内核分析之扒开系统调用的三层皮（上）
- idoc 和 bapi 和 rfc 之间的区别
- Codeforces Round #329 (Div. 2)
- Tornado服务器的学习
- .Net (MVC) 随机生成验证码
- Python守护进程（多线程开发）
- CSS 代码是什么?（转）
- 关于bat文件语法
- Android Studio自定义注释模板及生成JavaDoc
- python学习-面向对象
- sql分区文件删不的可能解决方法
- Java实现贪吃蛇游戏【代码】
- Makefile学习(三)[第二版]
- Robust Principal Component Analysis?（PCP）
- jQuery的版本兼容问题
- vs code軟件操作
- 【设计经验】1、Verilog中如何规范的处理inout信号