P2902 [USACO08MAR]珍珠配对Pearl Pairing

    • 458通过
    • 1.1K提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 背包 贪心 USACO 2008 Special Judge
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    At Bessie's recent birthday party, she received N (2 <= N <= 100,000; N%2 == 0) pearls, each painted one of C different colors (1 <= C <= N).

    Upon observing that the number of pearls N is always even, her creative juices flowed and she decided to pair the pearls so that each pair of pearls has two different colors.

    Knowing that such a set of pairings is always possible for the supplied testcases, help Bessie perform such a pairing. If there are multiple ways of creating a pairing, any solution suffices.

    在Bessie最近的生日聚会上,她收到N(2<=N<=100,000; N%2==0)珍珠,每个都涂上C种不同颜色之一(1<=C<=N)。

    观察到珍珠N的数量总是均匀的,她的创意来了,决定配对珍珠,使每双珍珠有两种不同的颜色。数据保证存在答案。请帮助Bessie执行这样的配对,如果有多种创建配对的方法,任意输出即可(不过这里没有spj)。

    输入输出格式

    输入格式:

    * Line 1: Two space-separated integers: N and C

    * Lines 2..C + 1: Line i+1 tells the count of pearls with color i: C_i

    行1:两个空格分隔的整数:N和C。

    行2…C+1:行i+1为颜色i:C_i的珍珠数。

    输出格式:

    * Lines 1..N/2: Line i contains two integers a_i and b_i indicating that Bessie can pair two pearls with respective colors a_i and b_i.

    行1…N/2:行i包含两个整数a_i和b_i,表示Bessie可以将两个珍珠与各自的颜色a_i和b_i配对。

    输入输出样例

    输入样例#1: 复制
    8 3 
    2 
    2 
    4 
    
    输出样例#1: 复制
    1 3 
    1 3 
    2 3 
    3 2 
    

    说明

    There are 8 pearls and 3 different colors. Two pearls have color I; two have color II; four have color III.

    Bessie pairs each pearl of color III with one of color I and II.

    说明 有8颗珍珠和3种不同的颜色。两个珍珠颜色为1; 两个颜色为2; 四个颜色为3。

    Bessie将每种颜色3的珍珠与一种颜色1和2配对。

    感谢@ 线段木 提供的翻译

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。