2001 : Backup
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)
คุณเปิดบริษัทรับสำรองข้อมูลให้ลูกค้าที่เป็นสำนักงานขนาดใหญ่ ซึ่งคุณก็รู้อยู่ว่าเป็นงานที่ไม่สนุก คุณจึงออกแบบระบบสำรองข้อมูลให้สำนักงานลูกค้าต่างๆ ทำการสำรองข้อมูลของกันและกันไปเอง ส่วนคุณจะได้นั่งเล่นเกมส์คอมพิวเตอร์อยู่ที่บ้านสบายใจ
สำนักงานลูกค้าทั้งหมดนั้น ตั้งอยู่บนถนนสายเดียวกัน วิธีการของคุณคือจับคู่ระหว่างสำนักงานเหล่านั้น แล้วเดินสายเครือข่ายระหว่างอาคารสำนักงานที่เป็นคู่กัน เพื่อให้สำนักงานที่เป็นคู่กัน สำรองข้อมูลซึ่งกันและกัน
แต่ทว่าสายเครือข่ายนั้นมีราคาแพง บริษัทสื่อสารที่รับเดินสายจะเดินให้เพียง k เส้นเท่านั้น ซึ่งหมายความว่าคุณจะสร้างคู่สำนักงานเพื่อสำรองข้อมูลได้ k คู่เท่านั้น (นับเป็นจำนวนสำนักงานทั้งสิ้น 2k แห่ง) ทั้งนี้ต้องไม่มีสำนักงานใดมีสายเครือข่ายเข้าถึงเกินหนึ่งเส้น (หมายถึงว่าสำนักงานทั้ง 2k แห่งจะต้องต่างกันหมด)
นอกจากนี้บริษัทสื่อสารที่รับเดินสายยังเก็บค่าสายตามความยาวเป็นกิโลเมตร หมายความว่าคุณจะต้องจับคู่สำนักงานทั้ง k คู่ให้ใช้สายเครือข่ายสั้นที่สุดเท่าที่จะทำได้ กล่าวคือต้องจัดคู่สำนักงาน ในลักษณะที่ เมื่อนำระยะห่างระหว่างแต่ละคู่มารวมกันแล้ว ระยะรวมต้องสั้นที่สุดเท่าที่จะทำได้
เพื่อเป็นตัวอย่าง สมมุติว่ามีสำนักงานลูกค้าห้าแห่งอยู่บนถนนดังรูป สำนักงานเหส่านี้อยู่ห่าง ๑ กม., ๓ กม., ๔ กม., ๖ กม., และ ๑๒ กม. จากหัวถนน ตามลำดับ บริษัทสื่อสารกำหนดเดินสายให้คุณเพียง k = 2 เส้นเท่านั้น
ในกรณีนี้ การจับคู่ดีที่สุดคือ การเชื่อมสำนักงานที่หนึ่งและสองเข้าด้วยกัน และเชื่อมสำนักงานที่สามและสี่เข้าด้วยกัน ซึ่งจะใช้สายเครือข่ายจำนวน k = 2 เส้นตามที่กำหนด โดยเส้นแรกมีความยาว ๓ กม. – ๑ กม. = ๒ กม. และเส้นที่สองมีความยาว ๖ กม. – ๔ กม. = ๒ กม. การจับคู่เช่นนี้ จะใช้สายเครือข่ายความยาวรวม ๔ กม. ซึ่งสั้นที่สุดเท่าที่จะเป็นได้แล้ว
ข้อมูลนำเข้า
บรรทัดแรกในแฟ้มข้อมูลนำเข้า ประกอบด้วยจำนวนเต็ม n และ k แสดงถึงจำนวนสำนักงานลูกค้าบนถนนสายนี้ (1≤ n ≤ 100 000) และจำนวนสายเครือข่ายที่มีให้ใช้ (1 ≤ k ≤ n/2) ตามลำดับ
ต่อจากนั้นอีก n บรรทัด แต่ละบรรทัดจะมีจำนวนเต็มเพียงค่าเดียว (0 ≤ s ≤ 1 000 000 000) แสดงถึงระยะทางของแต่ละสำนักงาน นับจากหัวถนน ค่าเหล่านี้จะเรียงลำดับมาแล้ว จากค่าน้อยที่สุดถึงมากที่สุด
ข้อมูลส่งออก
ข้อมูลที่เขียนแสดงในแฟ้มข้อมูลส่งออก ควรจะประกอบด้วยค่าจำนวนเต็มเพียงค่าเดียว แสดงระยะทางรวมของสายเครือข่ายที่ต้องใช้ในการเชื่อมสำนักงาน 2k แห่งเข้าเป็น k คู่
ที่มา: Asia-Pacific Informatics Olympiad 2007
ความช่วยเหลือ: Hint[1] Hint[2]
สำนักงานลูกค้าทั้งหมดนั้น ตั้งอยู่บนถนนสายเดียวกัน วิธีการของคุณคือจับคู่ระหว่างสำนักงานเหล่านั้น แล้วเดินสายเครือข่ายระหว่างอาคารสำนักงานที่เป็นคู่กัน เพื่อให้สำนักงานที่เป็นคู่กัน สำรองข้อมูลซึ่งกันและกัน
แต่ทว่าสายเครือข่ายนั้นมีราคาแพง บริษัทสื่อสารที่รับเดินสายจะเดินให้เพียง k เส้นเท่านั้น ซึ่งหมายความว่าคุณจะสร้างคู่สำนักงานเพื่อสำรองข้อมูลได้ k คู่เท่านั้น (นับเป็นจำนวนสำนักงานทั้งสิ้น 2k แห่ง) ทั้งนี้ต้องไม่มีสำนักงานใดมีสายเครือข่ายเข้าถึงเกินหนึ่งเส้น (หมายถึงว่าสำนักงานทั้ง 2k แห่งจะต้องต่างกันหมด)
นอกจากนี้บริษัทสื่อสารที่รับเดินสายยังเก็บค่าสายตามความยาวเป็นกิโลเมตร หมายความว่าคุณจะต้องจับคู่สำนักงานทั้ง k คู่ให้ใช้สายเครือข่ายสั้นที่สุดเท่าที่จะทำได้ กล่าวคือต้องจัดคู่สำนักงาน ในลักษณะที่ เมื่อนำระยะห่างระหว่างแต่ละคู่มารวมกันแล้ว ระยะรวมต้องสั้นที่สุดเท่าที่จะทำได้
เพื่อเป็นตัวอย่าง สมมุติว่ามีสำนักงานลูกค้าห้าแห่งอยู่บนถนนดังรูป สำนักงานเหส่านี้อยู่ห่าง ๑ กม., ๓ กม., ๔ กม., ๖ กม., และ ๑๒ กม. จากหัวถนน ตามลำดับ บริษัทสื่อสารกำหนดเดินสายให้คุณเพียง k = 2 เส้นเท่านั้น
ในกรณีนี้ การจับคู่ดีที่สุดคือ การเชื่อมสำนักงานที่หนึ่งและสองเข้าด้วยกัน และเชื่อมสำนักงานที่สามและสี่เข้าด้วยกัน ซึ่งจะใช้สายเครือข่ายจำนวน k = 2 เส้นตามที่กำหนด โดยเส้นแรกมีความยาว ๓ กม. – ๑ กม. = ๒ กม. และเส้นที่สองมีความยาว ๖ กม. – ๔ กม. = ๒ กม. การจับคู่เช่นนี้ จะใช้สายเครือข่ายความยาวรวม ๔ กม. ซึ่งสั้นที่สุดเท่าที่จะเป็นได้แล้ว
ข้อมูลนำเข้า
บรรทัดแรกในแฟ้มข้อมูลนำเข้า ประกอบด้วยจำนวนเต็ม n และ k แสดงถึงจำนวนสำนักงานลูกค้าบนถนนสายนี้ (1≤ n ≤ 100 000) และจำนวนสายเครือข่ายที่มีให้ใช้ (1 ≤ k ≤ n/2) ตามลำดับ
ต่อจากนั้นอีก n บรรทัด แต่ละบรรทัดจะมีจำนวนเต็มเพียงค่าเดียว (0 ≤ s ≤ 1 000 000 000) แสดงถึงระยะทางของแต่ละสำนักงาน นับจากหัวถนน ค่าเหล่านี้จะเรียงลำดับมาแล้ว จากค่าน้อยที่สุดถึงมากที่สุด
ข้อมูลส่งออก
ข้อมูลที่เขียนแสดงในแฟ้มข้อมูลส่งออก ควรจะประกอบด้วยค่าจำนวนเต็มเพียงค่าเดียว แสดงระยะทางรวมของสายเครือข่ายที่ต้องใช้ในการเชื่อมสำนักงาน 2k แห่งเข้าเป็น k คู่
ที่มา: Asia-Pacific Informatics Olympiad 2007
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 5 2 1 3 4 6 12 | 4 |
ความช่วยเหลือ: Hint[1] Hint[2]
กำลังออนไลน์: 20 ผู้เยี่ยมชมและ 0 สมาชิก (0 บอท)