昨晚的Atcoder ABC Contest 431第四题要用到动态规划，所以我又只能repeat ABC。动态规划，心里永远的痛。至于Atcoder ABC Contest 430为啥没写日志，因为430第一题就令人迷惑。
A - Robot Balance
Time Limit: 2 sec / Memory Limit: 1024 MiB
Score : 100 points
Problem Statement
Takahashi can combine a head part and a body part to create a robot. A robot falls over if the weight of the head part is greater than the weight of the body part.Currently, he has one head part and one body part. The weight of the head part is H grams, and the weight of the body part is B grams.He wants to make the body part heavier so that the robot does not fall over. Find how many more grams the body part needs to be made heavier so that his robot does not fall over.
Constraints
1≤H≤100
1≤B≤100
All input values are integers.
Input
The input is given from Standard Input in the following format:
H B
Output
Print the answer.
我的解
h,b = gets.split(" ").map(&:to_i)
puts [h-b,0].max
B - Robot Weight
Time Limit: 2 sec / Memory Limit: 1024 MiB
Score : 200 points
Problem Statement
There is a robot, and initially the weight of the robot is X. This robot has N types of parts that can be attached simultaneously: type1, type2,…, typeN. The weight of the type
i (1≤i≤N) part is Wi. Initially, none of the N types of parts are attached to the robot.
Process the following Q queries in order. The i-th query (1≤i≤Q) is represented by an integer Pi and is as follows:
If the type Pi part is not currently attached to the robot, attach it; if it is attached, remove it. Then, print the current weight of the robot.
Constraints
1≤X≤100
1≤N≤100
1≤Wi≤100 (1≤i≤N)
1≤Q≤100
1≤Pi ≤N (1≤i≤Q)
All input values are integers.
Input
The input is given from Standard Input in the following format:
X
N
W1 W2 … WN
Q
P1
P2
⋮
PQ
Output
Output Q lines. The i-th line (1≤i≤Q) should contain the result of processing the i-th query.
我的解
x = gets.to_i
n = gets.to_i
num = gets.split(" ").map(&:to_i)
q = gets.to_i
h = {}
q.times do
y = gets.to_i
unless h.key?(y)
puts x+num[y-1]
x += num[y-1]
h[y] = 1
else
x -= num[y-1]
h.delete(y)
puts x
end
end
C - Robot Factory
Time Limit: 2 sec / Memory Limit: 1024 MiB
Score : 300 points
Problem Statement
Takahashi can combine a head part and a body part to create a robot. A robot falls over if the weight of the head part is greater than the weight of the body part.
Currently, he has N head parts and M body parts. The weight of the i-th (1≤i≤N) head part is Hi grams, and the weight of the i-th (1≤i≤M) body part is Bi grams.
He wants to create a total of K robots that do not fall over by appropriately combining the parts he has. Determine whether he can achieve his goal by combining the parts well.
Here, a part cannot be used to create multiple robots, and two or more head parts (or two or more body parts) cannot be used to create one robot.
Constraints
1≤N≤2×10**5
1≤M≤2×10**5
1≤K≤min{N,M}
1≤Hi ≤10**9 (1≤i≤N)
1≤Bi ≤10**9 (1≤i≤M)
All input values are integers.
Input
The input is given from Standard Input in the following format:
N M K
H1 H2 … HN
B1 B2 … BM
Output
Print Yes if Takahashi can combine the parts well to create K robots that do not fall over; otherwise, print No.
我的解
require "rbtree"
n, m, k = gets.split(" ").map(&:to_i)
h = gets.split(" ").map(&:to_i)
b = gets.split(" ").map(&:to_i)
h.sort!
b.sort!
cnt = 0
x = b.bsearch_index { |i| i >= h[0] }
cnt = 0
if x.nil?
puts "No"
else
if x == m - 1 && k > 1
puts "No"
exit
elsif x == m - 1 && k == 1
puts "Yes"
exit
else
cnt += 1
t = RBTree.new
for i in x + 1...m
if t.has_key?(b[i])
t[b[i]] += 1
else
t[b[i]] = 1
end
end
for i in 1...n
x = t.lower_bound(h[i])
if x.nil?
if cnt < k
puts "No"
exit
else
puts "Yes"
exit
end
else
t[x[0]] -= 1
if t[x[0]] == 0
t.delete(x[0])
cnt += 1
else
cnt += 1
end
if cnt == k
puts "Yes"
exit
end
end
end
puts "No"
end
end
