AcWing 3075. 秦腾与教学评估(Java)
原题链接
困难
作者:
上杉
,
2021-05-03 14:33:33
,
所有人可见
,
阅读 275
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
/**
* @program: 算法题
* @author: 上杉
* @create: 2021-05-03 14:06
**/
public class Main {
static Group[] groups;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(bf.readLine());
while (T-- > 0){
int n = Integer.parseInt(bf.readLine());
groups = new Group[n];
for (int i = 0; i < n; i++) {
String[] numString = bf.readLine().split(" ");
int start = Integer.parseInt(numString[0]);
int end = Integer.parseInt(numString[1]);
int d = Integer.parseInt(numString[2]);
groups[i] = new Group(start,end,d);
}
Arrays.sort(groups);
long l = 1;
long r = Integer.MAX_VALUE;
while (l < r){
long mid = (l + r) >> 1;
int sum = sum(mid);
if ((sum & 1) == 1){
//奇数
r = mid;
}else {
l = mid + 1;
}
}
if ((sum(r) & 1) == 1){
//统计该点的人数
int count = 0;
for (int i = 0; i < n; i++) {
if (groups[i].end < r){
continue;
}
if (groups[i].start > r){
break;
}
if ((r - groups[i].start) % groups[i].d == 0){
count ++;
}
}
System.out.println(r+" "+ count);
}else {
System.out.println("Poor QIN Teng:(");
}
}
}
private static int sum(long mid) {
int index = 0;
int sum = 0;
while (index < groups.length && groups[index].start <= mid){
long e = Math.min(mid,groups[index].end);
long cnt = (e - groups[index].start) / groups[index].d + 1;
sum += cnt;index++;
}
return sum;
}
static class Group implements Comparable<Group>{
int start;
int end;
int d;
public Group(int start, int end, int d) {
this.start = start;
this.end = end;
this.d = d;
}
@Override
public int compareTo(Group o) {
return start - o.start;
}
}
}