西安电子科技大学计算机学院 ACMICPC程序设计概述ppt课件.ppt

ACM/ICPC程序设计概述 Agenda ACM/ICPC简介 题目示例 相关知识 相关网络资源 ACM/ICPC简介 由国际计算机界历史最悠久、最具权威性的组织ACM学会（Association for Computer Machinery）主办。目前，ACM国际大学生程序设计大赛已经成为参赛选手展示计算机才华的广阔舞台，是著名大学计算机教育成果的直接体现，也是信息企业与世界顶尖计算机人才对话的最好机会，因此，该赛事已逐步演变成一项全球高校间计算机学科实力的竞赛。 ACM/ICPC简介 ACM/ICPC竞赛题目难度大，更强调算法的效率，竞赛时3人合作，共用一台计算机，非常注重团队协作精神；很多题目没有成熟的算法，旨在考验参赛队员的创新能力；比赛现场完全封闭，现场提交程序、现场评判，能客观、公正地展现参赛学生的真实水平。 ACM/ICPC简介 ACM/ICPC简介 ACM/ICPC简介 常用环境 C++：gcc/g++、Kylix Java：jdk、eclipse 重点：语言的标准库 Agenda ACM/ICPC简介 题目示例 相关知识 相关网络资源 Machine Schedule Problem G: Machine Schedule (input file: machine.in) ? As we all know, machine scheduling is a very classical problem in computer science and has been studied for a very long history. Scheduling problems differ widely in the nature of the constraints that must be satisfied and the type of schedule desired. Here we consider a 2-machine scheduling problem. There are two machines A and B. Machine A has n kinds of working modes, which is called mode_0, mode_1, …, mode_n-1, likewise machine B has m kinds of working modes, mode_0, mode_1, … , mode_m-1. At the beginning they are both work at mode_0. Machine Schedule(cont.) For k jobs given, each of them can be processed in either one of the two machines in particular mode. For example, job 0 can either be processed in machine A at mode_3 or in machine B at mode_4, job 1 can either be processed in machine A at mode_2 or in machine B at mode_4, and so on. Thus, for job i, the constraint can be represent as a triple (i, x, y), which means it can be processed either in machine A at mode_x, or in machine B at mode_y. Obviously, to accomplish all the jobs, we need to change the machine’s working mode from time to time, but unfortunately, the machine’s working mode can only be changed by restarting it manually. By changing the sequence of the jobs and assigning each job to a suitable machine, please write a program to minimize the times of restarting machines. Machine Schedule(cont.) Input The input file for this program consists of