AcWing 133. 【java】蚯蚓
原题链接
中等
作者:
tt2767
,
2019-12-08 20:34:27
,
所有人可见
,
阅读 829
// 怎么发现这种规律呢?有普遍性么?
import java.util.*;
import java.util.stream.*;
public class Main{
void run(){
int n = jin.nextInt();
int m = jin.nextInt();
int q = jin.nextInt();
int u = jin.nextInt();
int v = jin.nextInt();
int t = jin.nextInt();
for (int i = 0; i < n ; i++) res.add(jin.nextInt());
Collections.sort(res);
Collections.reverse(res);
for (int i = 0; i < n ; i++) seg.offer(res.get(i));
res.clear();
int ex = 0;
for (int i = 1 ; i <= m ; i++){ // 这里细节比较多, 首先要从1开始才方便%
int s = select();
s += ex; // 先补齐成真实值
int l = (int) (s*1L*u/v);
int r = s - l;
if (i % t == 0) res.add(s);
ex += q;
left.offer(l-ex);
right.offer(r-ex);
}
String c_res = String.join(" ", res.stream().map(x->String.valueOf(x)).collect(Collectors.toList()));
System.out.println(c_res);
res.clear();
for (int i = 1 ; i<= m+n ;i++){
int s = select();
if (i % t == 0) res.add(s + ex);
}
c_res = String.join(" ", res.stream().map(x->String.valueOf(x)).collect(Collectors.toList()));
System.out.println(c_res);
}
Integer select (){
int max_value = Integer.MIN_VALUE;
if (!seg.isEmpty()) max_value = Math.max(seg.peek(), max_value);
if (!left.isEmpty()) max_value = Math.max(left.peek(), max_value);
if (!right.isEmpty()) max_value = Math.max(right.peek(), max_value);
if (!seg.isEmpty() && max_value == seg.peek()) return seg.poll();
if (!left.isEmpty() && max_value == left.peek()) return left.poll();
if (!right.isEmpty() && max_value == right.peek()) return right.poll();
return null;
}
private List<Integer> res = new ArrayList<>();
private Queue<Integer> seg = new LinkedList<>();
private Queue<Integer> left = new LinkedList<>();
private Queue<Integer> right = new LinkedList<>();
private Scanner jin = new Scanner(System.in);
public static void main(String[] args) throws Exception {new Main().run();}
}