Codejam 2020资格赛第3题… 逻辑有什么问题?

huangapple 未分类评论54阅读模式
英文:

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&lt;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 = &#39;C&#39;;   //Cameron
            char J = &#39;J&#39;;   //Jamie
            int flag = 0;   //1 if impossible
            
            
            for(int j=0; j&lt;N; j++)  //setting all slots to x
                y[j] = &#39;x&#39;;
            
            for(int j=0; j&lt;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&lt;N; j++){ //assigning rest of C&#39;s
                for(int k=0; k&lt;j; k++){
                    
                    if(y[k] == C){
                        if((S[j]&lt;S[k] &amp;&amp; E[j]&lt;= S[k]) || (S[j]&gt;=E[k] &amp;&amp; E[j]&gt; E[k])){
                            y[j] = C;
                        }
                        else{
                            y[j] = &#39;x&#39;;
                            break;
                        }
                    }
                }
            }
            
            
            for(int j=1; j&lt;N; j++){     //assigning J to first empty slot 
                if(y[j] == &#39;x&#39;){
                    y[j] = J;
                    break;
                }
            }
            
            for(int j=1; j&lt;N; j++){     //assigning rest of J&#39;s
                if(y[j] == &#39;x&#39;){
                    for(int k=0; k&lt;j; k++){
                    
                        if(y[k] == J){
                            if((S[j]&lt;S[k] &amp;&amp; E[j]&lt;= S[k]) || (S[j]&gt;=E[k] &amp;&amp; E[j]&gt; E[k])){
                                y[j] = J;
                            }
                            else{
                                y[j] = &#39;x&#39;;
                                break;
                            }
                        }
                    }
                }
                
            }
            
            for(int j=0; j&lt;N; j++){     //Check if there is empty slot
                if(y[j] == &#39;x&#39;){
                    flag = 1;
                    break;
                }
            }
            String Y = &quot;&quot;;  //Answer
            
            if(flag == 1){
                Y = &quot;IMPOSSIBLE&quot;;
                System.out.println(&quot;Case #&quot; + x + &quot;: &quot; + Y);
            }
                
            else{
                for(int j=0; j&lt;N; j++)
                    Y += y[j];
                
                System.out.println(&quot;Case #&quot; + x + &quot;: &quot; + 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

huangapple
  • 本文由 发表于 2020年4月9日 22:22:04
  • 转载请务必保留本文链接:https://java.coder-hub.com/61123367.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定