1065 A+B and C (64bit)

我不是女神ヾ 2022-04-15 00:42 200阅读 0赞

### problem description ###

Given three integers A, B and C in \[−263,263\], you are supposed to tell whether A+B>C.

### 题目描述 ###

给定\[−263，263\]中的三个整数A，B和C，你应该知道A B>C。

#### Input Specification: ####

The first line of the input gives the positive number of test cases, T (≤10). Then T test cases follow, each consists of a single line containing three integers A, B and C, separated by single spaces.

#### 输入格式： ####

输入的第一行给出了测试用例的正数，T(≤10)。然后是T测试用例，每一行包含三个整数A、B和C，由单个空格隔开。

#### Output Specification: ####

For each test case, output in one line Case \#X: true if A+B>C, or Case \#X: false otherwise, where X is the case number (starting from 1).

#### 输出格式： ####

对于每个测试用例，在一行中输出\#X：true如果A+B>C，或用例X：false否则，其中X是用例编号(从1开始)。

#### Sample Input: ####

3
    1 2 3
    2 3 4
    9223372036854775807 -9223372036854775808 0

#### 输入样例： ####

3
    1 2 3
    2 3 4
    9223372036854775807 -9223372036854775808 0

#### Sample Output: ####

Case #1: false
    Case #2: true
    Case #3: false

#### 输出样例： ####

Case #1: false
    Case #2: true
    Case #3: false

*思路*  
  由于 long long 的范围是 \[-263, 263)，因此题目中给出的两个整数相加有可能会溢出（正溢出或负溢出），直接进行大小判断会造成错误。在计算机组成原理中会指出，如果两个正数之和等于负数或是两个负数之和等于正数，那么就是溢出。  
  ① 当 A + B ≥ 263 时，显然有 A + B > C 成立，但 A + B 会因超过 long long 的正向最大值而发生正溢出。由于题目给定的 A 和 B 最大均为 263 \- 1 ，故 A + B 最大为 264 \- 2 ，因此使用 long long 存储正溢出后的值的区间为 \[-263, -2\]（由 ( 264 \- 2) % (2 64) = -2 可得右边界）。所以，当 A > 0, B > 0, A + B < 0 时为正溢出，输出 true。  
  ② 当 A + B < -263 时，显然有 A + B < C 成立，但 A + B 会因超过 long long 的负向最小值而发生负溢出。由于题目给定的 A 和 B 最小均为 -263，故 A + B 最小为 -264，因此使用 long long 存储负溢出后的值的区间为 \[0, 263)（由 (-264) % 264 = 0 可得左边界）。所以，当 A < 0，B < 0，A + B ≥ 0 时为负溢出，输出 false。  
  ③ 在没有溢出的情况下，当 A + B > C 时，输出 true；当 A + B ≤ C 时，输出 false。

*注意*  
  ① 经测试，数据中并没有 A 或 B 取到 263 的情况，因此题目中的数据范围可能是写错了，应该是 \[-263, 263) 才更符合数据，否则就要用带负数的大整数运算了（因为 long long 存储 263 时会自动变成 -263，无法区分左右边界）。  
  ② A + B必须存放到 long long 型变量中才可与 C 进行比较，而不可以在 if 的条件中直接相加与 C 比较，否则会造成后两组数据错误。

代码：

#include <stdio.h>
    int main() { 
    	int T, tcase = 1;
    	scanf("%d", &T);
    	while(T--) { 
    		long long a, b, c;
    		scanf("%lld%lld%lld", &a, &b, &c);
    		long long res = a + b; // res 存放 a + b 的结果 
    		bool flag;
    		if(a > 0 && b > 0 && res < 0) flag = true; // 正溢出为 true
    		else if(a < 0 && b < 0 && res >= 0)  flag = false; // 负溢出为 false
    		else if(res > c) flag = true; // 无溢出时， A + B > C时为 true
    		else flag = false;
    		if(flag == true) { 
    			printf("Case #%d: true\n", tcase++);
    		} else { 
    			printf("Case #%d: false\n", tcase++);
    		}
    	}
    	return 0;
    }

结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MTMxNjk5_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MTMxNjk5_size_16_color_FFFFFF_t_70]: /images/20220415/d8be8030bbfc4862b04e0b4e8728fb22.png