A1131 | [COCI-2007_2008-contest6]#1 CESTARINE
来源COCI
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
In a single day, N of Luka's trucks travel a specific highway. The highway has a number of exits and entrances. An exit with a particular number is in the same location as the entrance with that number.
Upon entering the highway, a truck driver receives a ticket which indicates the entrance he used. When exiting, the driver pays a toll equal to the absolute difference of the entrance and exit numbers. For example, if a ticket says he used entrance 30, then exiting at exit 12 will cost him 1
8.
Luka has figured out a way to save toll money that his company daily spends. Any two drivers can meet on the highway and exchange tickets, even if their routes don't overlap. Tickets can be exchanged an arbitrary number of times.
However, a driver cannot use an exit if his ticket says he used the same entrance, since that would be suspicious.
Write a program that calculates the least total amount of tolls that the drivers can achieve by exchanging tickets.
Upon entering the highway, a truck driver receives a ticket which indicates the entrance he used. When exiting, the driver pays a toll equal to the absolute difference of the entrance and exit numbers. For example, if a ticket says he used entrance 30, then exiting at exit 12 will cost him 1
8.
Luka has figured out a way to save toll money that his company daily spends. Any two drivers can meet on the highway and exchange tickets, even if their routes don't overlap. Tickets can be exchanged an arbitrary number of times.
However, a driver cannot use an exit if his ticket says he used the same entrance, since that would be suspicious.
Write a program that calculates the least total amount of tolls that the drivers can achieve by exchanging tickets.
输入格式
The first line contains the integer N (1 ≤ N ≤ 100000), the number of trucks.
Each of the following N lines contains two distinct integers between 1 and 100000
0. These are in order the entrance and exit numbers of one truck.
No two trucks will use the same highway entrance or the same exit.
Each of the following N lines contains two distinct integers between 1 and 100000
0. These are in order the entrance and exit numbers of one truck.
No two trucks will use the same highway entrance or the same exit.
输出格式
Output the least total amount of tolls Luka's company must pay.
Note: use 64-bit integer types (long long in C/C++, int64 in Pascal).
Note: use 64-bit integer types (long long in C/C++, int64 in Pascal).
输入输出样例
输入 #1
3 3 65 45 10 60 25
输出 #1
32
输入 #2
3 5 5 6 7 8 8
输出 #2
5
In the first example, the first and third drivers will exchange tickets. After this, the second and third
drivers exchange tickets. After this, the drivers will have the tickets 60, 3, 45, respectively. The total
amount in tolls is |65−60| + |10−3| + |25−45| = 32.
drivers exchange tickets. After this, the drivers will have the tickets 60, 3, 45, respectively. The total
amount in tolls is |65−60| + |10−3| + |25−45| = 32.
C++ 编辑器
输入
输出
可保存默认模板;新题优先使用已保存模板。
当前快捷键仅展示,暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好,我是作答助手。可以问思路、复杂度、样例含义或代码报错原因;不会直接给出完整 AC 代码。
确定要清空代码吗?
提交通过
评测结果:Accepted