이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
import java.io.*;
import java.util.*;
public class bridge {
public static PriorityQueue<Long> left; public static PriorityQueue<Long> right;
public static long lSum; public static long rSum; //We have distance = \sum_{i} |S_i - bridge| + |T_i-bridge|
//If we pick the median as the bridge (which is optimal), then there are an equal amount of S_i or T_i > bridge as < bridge
//(if odd, the bridge = median, so difference = 0). Thus, the -x and +x all cancel, leaving distance = rSum - lSum.
public static void main(String[] args) throws IOException {
BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer l1 = new StringTokenizer(scan.readLine());
int k = Integer.parseInt(l1.nextToken()); int tot = Integer.parseInt(l1.nextToken()); int num = 0; ArrayList<Integer> idxs = new ArrayList<>();
long[][] arrTemp = new long[tot][4]; long constant = 0; //Distance for same shore house-work pairs.
for (int i = 0;i<tot;i++) {
StringTokenizer st = new StringTokenizer(scan.readLine()); String s = st.nextToken();
arrTemp[i][0] = s.charAt(0)-'A'; arrTemp[i][1] = s.charAt(1)-'0'; arrTemp[i][2] = s.charAt(2)-'A'; arrTemp[i][3] = s.charAt(3)-'0';
if (arrTemp[i][0]==arrTemp[i][2]) {
constant += Math.abs(arrTemp[i][1]-arrTemp[i][3]);
} else {
num++; idxs.add(i);
}
}
long[][] arr = new long[num][2]; //Filtered to only the house-work pairs that are not on the same bank.
int idx = 0;
for (int i : idxs) {
arr[idx][0] = arrTemp[i][1]; arr[idx][1] = arrTemp[i][3]; idx++;
}
Arrays.sort(arr,(i,j)-> (int) ((i[0]+i[1])-(j[0]+j[1])));
/*for (int i = 0;i<num;i++) {
System.out.println(arr[i][0]+" "+arr[i][1]);
}*/
clean(); long ans;
long[] prefix = new long[num+1]; //Prefix of all the answers if we have cows 0 to i
for (int i = 0;i<num;i++) {
insert(arr[i][0]); insert(arr[i][1]);
//System.out.println(left+" "+right);
prefix[i+1] = rSum - lSum;
}
ans = prefix[num];
if (k==2) { //Iterate through all possible partitioning spots.
clean();
for (int i = num; i>0; i--) {
insert(arr[i][0]); insert(arr[i][1]);
ans = Math.min(ans, rSum - lSum + prefix[i - 1]);
}
}
System.out.println(ans+constant+num);
}
public static void insert (long x) {
long median = (left.size()>0 ? left.peek() : 1000000001);
if (x<=median) { //Insert to left
left.add(x); lSum += x;
} else { //Insert to right
right.add(x); rSum += x;
}
//Check sizes. We want left.size = right.size + (0 or 1)
if (right.size()+1<left.size()) { //Add to right
long temp = left.peek();
left.poll(); right.add(temp);
lSum -= temp; rSum += temp;
} else if (left.size()<right.size()) { //Add to left
long temp = right.peek();
right.poll(); left.add(temp);
rSum -= temp; lSum += temp;
}
}
public static void clean () {
left = new PriorityQueue<>((a,b)-> (int) (b-a)); right = new PriorityQueue<>((a,b)-> (int) (a-b));
lSum = 0; rSum = 0;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |