codeforces B. Simple Molecules 解题报告

题目链接：http://codeforces.com/problemset/problem/344/B

题目意思：这句话是解题的关键： The number of bonds of an atom in the molecule must be equal to its valence number。 给定三个原子的化学价，规定化学价数等于该原子与另外两个原子所连接的原子键之和。

       又一次把简单问题复杂化了.....（以下注释部分读者可以忽略）

      /*

       一开始三重循环枚举，绝对超时（10^6 * 10^6 * 10^6），不敢提交！！后来甚至想到这三个原子构成的原子键与总的化学价数成两倍关系（貌似没什么用，也好像不太正确，最后觉得无法实施，没深究下去了）......昨天上课再想，想到把这三个数从小到大排序，然后枚举最小和次小的原子的原子键，这样枚举出的值最大也不会超过最小的那个原子的价数，知道其中两个原子的原子键后，其余两个原子键自然就能计算出来。（例如8  3 11，3和8连接的原子键最大只可能是3）这样做，虽然在一般情况下（不考虑极端的10^6），枚举的范围小了，然而这三个原子的输入顺序在排序的过程中被改变了，用结构体保存原来输入的序号？越来越不可行了......

   */

    今天硬着头皮，做好TLE的心理准备，不排序直接枚举（1～10^6）输入的前两个数的原子键数，一旦发现直接输出。其实三个原子键构成这样一个关系：假设输入的是a，b，c，枚举a，b之间的原子键数i（0<= i <= 10^6 )。想到b、c原子键数符合：b - i ；a、c之间的原子键符合：a - i。最后如果符合 (a -  i ) + (b - i ) = c，即找出一组解。

  

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

const int maxn = 1e6 + 10;

int main()
{
    int a, b, c, i;
    while (scanf("%d%d%d", &a, &b, &c) != EOF)
    {
        int flag = 0;
        for (i = 0; i <= maxn; i++)
        {
            if (a + b - 2 * i == c && b-i >= 0 && a-i >= 0)   // 一定要判断 b-i 和 a-i 的取值，负数的需要排序
            {
                flag = 1;  // 找出一组解，直接跳出循环
                printf("%d %d %d\n", i, b-i, a-i);
                break;    
            }
        }
        if (!flag)
            printf("Impossible\n");
    }
    return 0;
}