英文:
Codejam 2020 Qualification Round Problem 3... What's wrong with the logic?
问题
以下是您提供的代码的翻译部分:
import java.lang.*;
import java.util.*;
import java.io.*;
public class Solution {
public static void main (String [] args){
// Scanner
Scanner input = new Scanner(System.in);
int T = input.nextInt(); // 测试用例
for(int i=0; i<T; i++){
int x = i+1; // 测试用例编号
int N = input.nextInt();
int [] S = new int [N]; // 开始时间
int [] E = new int [N]; // 结束时间
char [] y = new char [N]; // 答案
char C = 'C'; // Cameron
char J = 'J'; // Jamie
int flag = 0; // 如果为1,则表示不可能
for(int j=0; j<N; j++) // 将所有插槽设置为x
y[j] = 'x';
for(int j=0; j<N; j++){ // 获取输入
S[j] = input.nextInt();
E[j] = input.nextInt();
}
y[0] = C; // 将C分配给第一个任务
for(int j=1; j<N; j++){ // 分配剩余的C
for(int k=0; k<j; k++){
if(y[k] == C){
if((S[j]<S[k] && E[j]<=S[k]) || (S[j]>=E[k] && E[j]>E[k])){
y[j] = C;
}
else{
y[j] = 'x';
break;
}
}
}
}
for(int j=1; j<N; j++){ // 分配J到第一个空插槽
if(y[j] == 'x'){
y[j] = J;
break;
}
}
for(int j=1; j<N; j++){ // 分配剩余的J
if(y[j] == 'x'){
for(int k=0; k<j; k++){
if(y[k] == J){
if((S[j]<S[k] && E[j]<=S[k]) || (S[j]>=E[k] && E[j]>E[k])){
y[j] = J;
}
else{
y[j] = 'x';
break;
}
}
}
}
}
for(int j=0; j<N; j++){ // 检查是否有空插槽
if(y[j] == 'x'){
flag = 1;
break;
}
}
String Y = ""; // 答案
if(flag == 1){
Y = "IMPOSSIBLE";
System.out.println("Case #" + x + ": " + Y);
}
else{
for(int j=0; j<N; j++)
Y += y[j];
System.out.println("Case #" + x + ": " + Y );
}
}
}
}
请注意,您提供的代码似乎存在一些逻辑错误。如果您能提供更多关于代码输出"Wa"的错误信息或问题细节,我将能够更好地帮助您找到错误所在。
英文:
The way I approached was to create 3 arrays: one for starting time of each event, one for ending time, and one for a possible distribution of tasks. I reset the third array to contain 'x' for every element. Then I first assign all possible tasks to Cameron by checking if a task overlaps with any previously assigned task using this logic:
- If (starting time of new task < starting time of assigned task AND ending time of new task <= starting time of assigned task) OR (starting time of new task >= ending time of new task AND ending time of new task > ending time of assigned task) THEN this new task doesn't overlap and can be assigned to Cameron.
I then follow a similar logic to assign tasks to Jamie. Then I print IMPOSSIBLE if there is one of more empty slots, else the answer. Please check the code:
import java.lang.*;
import java.util.*;
import java.io.*;
public class Solution {
public static void main (String [] args){
//Scanner
Scanner input = new Scanner(System.in);
int T = input.nextInt(); //test cases
for(int i=0; i<T; i++){
int x = i+1; //test case number
int N = input.nextInt();
int [] S = new int [N]; //start time
int [] E = new int [N]; //end time
char [] y = new char [N]; //answer
char C = 'C'; //Cameron
char J = 'J'; //Jamie
int flag = 0; //1 if impossible
for(int j=0; j<N; j++) //setting all slots to x
y[j] = 'x';
for(int j=0; j<N; j++){ //taking input
S[j] = input.nextInt();
E[j] = input.nextInt();
}
y[0] = C; //assigning C to first task
for(int j=1; j<N; j++){ //assigning rest of C's
for(int k=0; k<j; k++){
if(y[k] == C){
if((S[j]<S[k] && E[j]<= S[k]) || (S[j]>=E[k] && E[j]> E[k])){
y[j] = C;
}
else{
y[j] = 'x';
break;
}
}
}
}
for(int j=1; j<N; j++){ //assigning J to first empty slot
if(y[j] == 'x'){
y[j] = J;
break;
}
}
for(int j=1; j<N; j++){ //assigning rest of J's
if(y[j] == 'x'){
for(int k=0; k<j; k++){
if(y[k] == J){
if((S[j]<S[k] && E[j]<= S[k]) || (S[j]>=E[k] && E[j]> E[k])){
y[j] = J;
}
else{
y[j] = 'x';
break;
}
}
}
}
}
for(int j=0; j<N; j++){ //Check if there is empty slot
if(y[j] == 'x'){
flag = 1;
break;
}
}
String Y = ""; //Answer
if(flag == 1){
Y = "IMPOSSIBLE";
System.out.println("Case #" + x + ": " + Y);
}
else{
for(int j=0; j<N; j++)
Y += y[j];
System.out.println("Case #" + x + ": " + Y );
}
}
}
}
I keep getting a WA for some reason. Why is the logic incorrect?
答案1
得分: 0
代替创建3个数组,您应该创建许多每个包含3个元素(开始时间,结束时间,条目索引)的数组,然后根据开始时间对这些数组进行排序。这是一个无权重区间调度问题,您可以在这里查看描述:http://www.cse.psu.edu/~ads22/courses/cmpsc465/S12/lec-notes/CMPSC465-S12-Lec-17-greedy-algs.pptx.pdf
英文:
instead of creating 3 arrays, you should create many arrays with 3 elements each, (starttime, endtime, entryindex). Then sort these arrays according to starttime. This is a unweighted interval scheduling problem, you can have a look at the description here:http://www.cse.psu.edu/~ads22/courses/cmpsc465/S12/lec-notes/CMPSC465-S12-Lec-17-greedy-algs.pptx.pdf
专注分享java语言的经验与见解,让所有开发者获益!
评论