A5434. 冰淇淋
编程题
普及-
知识点
题目描述
我们有 $N$ 杯冰淇淋。
每杯 $i$ 的口味和美味分别是 $F_i$ 和 $S_i$ （ $S_i$ 是偶数）。
您将选择并吃掉两杯 冰淇淋 。
您的满意度定义如下
- 设 $s$ 和 $t$ （ $s \ge t$ ）是所吃杯子的美味程度。
- 如果两杯的味道不同，则您的满意度为 $\displaystyle s+t$ 。
- 否则，你的满意度为 $\displaystyle s + \frac{t}{2}$ 。
求可达到的最大满意度。
每杯 $i$ 的口味和美味分别是 $F_i$ 和 $S_i$ （ $S_i$ 是偶数）。
您将选择并吃掉两杯 冰淇淋 。
您的满意度定义如下
- 设 $s$ 和 $t$ （ $s \ge t$ ）是所吃杯子的美味程度。
- 如果两杯的味道不同，则您的满意度为 $\displaystyle s+t$ 。
- 否则，你的满意度为 $\displaystyle s + \frac{t}{2}$ 。
求可达到的最大满意度。
输入格式
第一行输入一个整数 $N$，代表有 $N$ 杯冰淇淋。
接下来一共 $N$ 行，每行给出两个整数 $F_i, S_i$, 代表冰淇淋的口味和美味。
接下来一共 $N$ 行，每行给出两个整数 $F_i, S_i$, 代表冰淇淋的口味和美味。
输出格式
将答案打印为整数。
输入输出样例
输入 #1
4 1 4 2 10 2 8 3 6
输出 #1
16
输入 #2
4 4 10 3 2 2 4 4 12
输出 #2
17
说明/提示
**【数据范围】**
- 所有输入值均为整数。
- $2 \le N \le 3 \times 10^5$
- $1 \le F_i \le N$
- $2 \le S_i \le 10^9$
- $S_i$ 为偶数。
对于样例1
考虑吃第二杯和第四杯。
- 第二杯的味道是 $2$ ，美味是 $10$ 。
- 第四杯的味道是 $3$ ，可口度是 $6$ 。
- 由于它们的口味不同，您的满意度为 $10+6=16$ 。
因此，你可以获得 $16$ 的满足感。
你无法获得大于 $16$ 的满足感。
对于样例2
考虑吃掉第一杯和第四杯。
- 第一杯的味道是 $4$ ，美味是 $10$ 。
- 第四杯的味道是 $4$ ，美味度是 $12$ 。
- 由于它们的味道相同，您的满意度为 $12+\frac{10}{2}=17$ 。
因此，你可以获得 $17$ 的满足感。
您无法获得大于 $17$ 的满意度。
- 所有输入值均为整数。
- $2 \le N \le 3 \times 10^5$
- $1 \le F_i \le N$
- $2 \le S_i \le 10^9$
- $S_i$ 为偶数。
对于样例1
考虑吃第二杯和第四杯。
- 第二杯的味道是 $2$ ，美味是 $10$ 。
- 第四杯的味道是 $3$ ，可口度是 $6$ 。
- 由于它们的口味不同，您的满意度为 $10+6=16$ 。
因此，你可以获得 $16$ 的满足感。
你无法获得大于 $16$ 的满足感。
对于样例2
考虑吃掉第一杯和第四杯。
- 第一杯的味道是 $4$ ，美味是 $10$ 。
- 第四杯的味道是 $4$ ，美味度是 $12$ 。
- 由于它们的味道相同，您的满意度为 $12+\frac{10}{2}=17$ 。
因此，你可以获得 $17$ 的满足感。
您无法获得大于 $17$ 的满意度。