Orange Boy Can You Solve It Out? Ep.8

思考题 for stupid myself

A well-known task

Given N segments [L_i,R_i] with weight W_i.
Now you want to choose some segments s_1,s_2,s_3,...,s_k so that |[L_{s_1},R_{s_1}]\cap [L_{s_2},R_{s_2}]\cap ...\cap [L_{s_k},R_{s_k}]|*\sum_{i=1}^kW_{s_i} is maximum.
|S| means the number of integers in the set S. K is decided by yourself.

Example

Input
{[1,5],w=3}
{[2,4],w=5}
{[3,5],w=1}
Output
Explain
choose 1 -> 5\times3=15 [1,5]
choose 2 -> 3\times5=15 [2,4]
choose 3 -> 3\times1=3 [3,5]
choose 1,2 -> 3\times(3+5)=24 [2,4]
choose 1,3 -> 3\times(3+1)=12 [3,5]
choose 2,3 -> 2\times(5+1)=12 [3,4]
choose 1,2,3 -> 2\times(3+5+1)=18 [3,4]

Constriants

Subtask 1(10%):N\leq10
Subtask 2(20%):N\leq100
Subtask 3(30%):N\leq1000
Subtask 4(40%):N\leq10^5
The author can get 60%(30%)
Orange boy will get AC quickly!

Slow (or Maybe Wrong) Solution By Weak XGN

Sort the segments by L. Then for each L we choose all segments with L'\leq L then we sort the chosen segments by R. Then we brute force which segments to choose.
Time Complexity is O(n^2log_n)
Proof Required

版权声明:
作者:XGN
链接:https://blog.hellholestudios.top/archives/177
来源:Hell Hole Studios Blog
文章版权归作者所有,未经允许请勿转载。

THE END
分享
二维码
< <上一篇
下一篇>>