「NOIP 2018普及组」龙虎斗

题目描述

轩轩和凯凯正在玩一款叫《龙虎斗》的游戏，游戏的棋盘是一条线段，线段上有 n个兵营（自左至右编号 1 ∼n），相邻编号的兵营之间相隔 1 厘米，即棋盘为长度为 n-1 厘米的线段。i 号兵营里有 ci位工兵。

下面图 1 为 n=6的示例：

轩轩在左侧，代表“龙”；凯凯在右侧，代表“虎”。 他们以 m 号兵营作为分界， 靠左的工兵属于龙势力，靠右的工兵属于虎势力，而第 m号兵营中的工兵很纠结，他们不属于任何一方。

一个兵营的气势为：该兵营中的工兵数 × 该兵营到 m 号兵营的距离；参与游戏 一方的势力定义为：属于这一方所有兵营的气势之和。

下面图 2 为 n = 6,m = 4 的示例，其中红色为龙方，黄色为虎方：

游戏过程中，某一刻天降神兵，共有 s1位工兵突然出现在了 p1号兵营。作为轩轩和凯凯的朋友，你知道如果龙虎双方气势差距太悬殊，轩轩和凯凯就不愿意继续玩下去了。为了让游戏继续，你需要选择一个兵营 p2，并将你手里的 s2位工兵全部派往 兵营 p2，使得双方气势差距尽可能小。

注意：你手中的工兵落在哪个兵营，就和该兵营中其他工兵有相同的势力归属（如果落在 m 号兵营，则不属于任何势力）。

输入格式

输入文件：fight.in 输入文件的第一行包含一个正整数n，代表兵营的数量。

接下来的一行包含 n 个正整数，相邻两数之间以一个空格分隔，第 i个正整数代 表编号为 i 的兵营中起始时的工兵数量 ci。

接下来的一行包含四个正整数，相邻两数间以一个空格分隔，分别代表 m,p1,s1,s2。

输出格式

输出文件：fight.out 输出文件有一行，包含一个正整数，即 p2，表示你选择的兵营编号。如果存在多个编号同时满足最优，取最小的编号。

样例

输入

6 
2 3 2 3 2 3 
4 6 5 2

Copy

输出

2

Copy

输入

6 
1 1 1 1 1 16 
5 4 1 1

Copy

输出

1

Copy

样例1说明

样例1：见问题描述中的图 2。

双方以 m=4号兵营分界，有 s1=5位工兵突然出现在p1=6号兵营。 龙方的气势为：

    2×(4−1)+3×(4−2)+2×(4−3)=14

虎方的气势为：

    2×(5−4)+(3+5)×(6−4)=18

当你将手中的 s2=2s2=2位工兵派往 p2=2号兵营时，龙方的气势变为：

    14+2×(4−2)=18

此时双方气势相等。

Copy

样例2：

双方以 m = 5号兵营分界，有 s1=1位工兵突然出现在 p1=4号兵营。

龙方的气势为：

    1×(5−1)+1×(5−2)+1×(5−3)+(1+1)×(5−4)=11

虎方的气势为：

    16×(6−5)=16

当你将手中的 s2=1位工兵派往 p2=1号兵营时，龙方的气势变为：

    11+1×(5−1)=15

此时可以使双方气势的差距最小。

Copy

数据范围与提示

1≤�≤�,1≤�1≤�1≤m≤n,1≤p1​≤n。

对于 20%20% 的数据，�=3,�=2,��=1,�1,�2≤100n=3,m=2,ci​=1,s1​,s2​≤100。 另有 20%20% 的数据，�≤10,�1=�,��=1,�1,�2≤100n≤10,p1​=m,ci​=1,s1​,s2​≤100。 对于 60%60% 的数据，�≤100,��=1,�1,�2≤100n≤100,ci​=1,s1​,s2​≤100。 对于 80%80% 的数据，�≤100,��,�1,�2≤100n≤100,ci​,s1​,s2​≤100。 对于 100%100% 的数据，�≤105n≤105,��,�1,�2≤109ci​,s1​,s2​≤109。 #D. [CSP-J 2021] 网络连接 A B C D E F 传统题 文件IO：network 1000ms 256MiB 题目描述 TCP/IP 协议是网络通信领域的一项重要协议。今天你的任务，就是尝试利用这个协议，还原一个简化后的网络连接场景。

在本问题中，计算机分为两大类：服务机（Server）和客户机（Client）。服务机负责建立连接，客户机负责加入连接。

需要进行网络连接的计算机共有 � n 台，编号为 1 ∼ � 1∼n，这些机器将按编号递增的顺序，依次发起一条建立连接或加入连接的操作。

每台机器在尝试建立或加入连接时需要提供一个地址串。服务机提供的地址串表示它尝试建立连接的地址，客户机提供的地址串表示它尝试加入连接的地址。

一个符合规范的地址串应当具有以下特征：

必须形如 a.b.c.d:e 的格式，其中 � , � , � , � , � a,b,c,d,e 均为非负整数； 0 ≤ � , � , � , � ≤ 255 0≤a,b,c,d≤255， 0 ≤ � ≤ 65535 0≤e≤65535； � , � , � , � , � a,b,c,d,e 均不能含有多余的前导 0 0。 相应地，不符合规范的地址串可能具有以下特征：

不是形如 a.b.c.d:e 格式的字符串，例如含有多于 3 3 个字符 . 或多于 1 1 个字符 : 等情况； 整数 � , � , � , � , � a,b,c,d,e 中某一个或多个超出上述范围； 整数 � , � , � , � , � a,b,c,d,e 中某一个或多个含有多余的前导 0 0。 例如，地址串 192.168.0.255:80 是符合规范的，但 192.168.0.999:80、192.168.00.1:10、192.168.0.1:088、192:168:0:1.233 均是不符合规范的。

如果服务机或客户机在发起操作时提供的地址串不符合规范，这条操作将被直接忽略。

在本问题中，我们假定凡是符合上述规范的地址串均可参与正常的连接，你无需考虑每个地址串的实际意义。

由于网络阻塞等原因，不允许两台服务机使用相同的地址串，如果此类现象发生，后一台尝试建立连接的服务机将会无法成功建立连接；除此之外，凡是提供符合规范的地址串的服务机均可成功建立连接。

如果某台提供符合规范的地址的客户机在尝试加入连接时，与先前某台已经成功建立连接的服务机提供的地址串相同，这台客户机就可以成功加入连接，并称其连接到这台服务机；如果找不到这样的服务机，则认为这台客户机无法成功加入连接。

请注意，尽管不允许两台不同的服务机使用相同的地址串，但多台客户机使用同样的地址串，以及同一台服务机同时被多台客户机连接的情况是被允许的。

你的任务很简单：在给出每台计算机的类型以及地址串之后，判断这台计算机的连接情况。

输入格式 第一行，一个正整数 � n。

接下来 � n 行，每行两个字符串 � � , � � op,ad，按照编号从小到大给出每台计算机的类型及地址串。

其中 � � op 保证为字符串 Server 或 Client 之一， � � ad 为一个长度不超过 25 25 的，仅由数字、字符 . 和字符 : 组成的非空字符串。

每行的两个字符串之间用恰好一个空格分隔开，每行的末尾没有多余的空格。

输出格式 输出共 � n 行，每行一个正整数或字符串表示第 � i 台计算机的连接状态。其中：

如果第 � i 台计算机为服务机，则：

如果其提供符合规范的地址串且成功建立连接，输出字符串 OK。 如果其提供符合规范的地址串，但由于先前有相同地址串的服务机而无法成功建立连接，输出字符串 FAIL。 如果其提供的地址串不是符合规范的地址串，输出字符串 ERR。 如果第 � i 台计算机为客户机，则：

如果其提供符合规范的地址串且成功加入连接，输出一个正整数表示这台客户机连接到的服务机的编号。 如果其提供符合规范的地址串，但无法成功加入连接时，输出字符串 FAIL。 如果其提供的地址串不是符合规范的地址串，输出字符串 ERR。 样例 #1 样例输入 #1 5 Server 192.168.1.1:8080 Server 192.168.1.1:8080 Client 192.168.1.1:8080 Client 192.168.1.1:80 Client 192.168.1.1:99999 样例输出 #1 OK FAIL 1 FAIL ERR 样例 #2 样例输入 #2 10 Server 192.168.1.1:80 Client 192.168.1.1:80 Client 192.168.1.1:8080 Server 192.168.1.1:80 Server 192.168.1.1:8080 Server 192.168.1.999:0 Client 192.168.1.1.8080 Client 192.168.1.1:8080 Client 192.168.1.1:80 Client 192.168.1.999:0 样例输出 #2 OK 1 FAIL FAIL OK ERR ERR 5 1 ERR 样例 #3 样例输入 #3 见附件中的 network/network3.in。 样例输出 #3 见附件中的 network/network3.ans。 样例 #4 样例输入 #4 见附件中的 network/network4.in。 样例输出 #4 见附件中的 network/network4.ans。 提示 【样例解释 #1】

计算机 1 1 为服务机，提供符合规范的地址串 192.168.1.1:8080，成功建立连接；

计算机 2 2 为服务机，提供与计算机 1 1 相同的地址串，未能成功建立连接；

计算机 3 3 为客户机，提供符合规范的地址串 192.168.1.1:8080，成功加入连接，并连接到服务机 1 1；

计算机 4 4 为客户机，提供符合规范的地址串 192.168.1.1:80，找不到服务机与其连接；

计算机 5 5 为客户机，提供的地址串 192.168.1.1:99999 不符合规范。

【数据范围】

测试点编号 � ≤ n≤ 特殊性质 1 1 10 10 性质 1 2 3 2 ∼ 3 2∼3 100 100 4 ∼ 5 4∼5 1000 1000 6 ∼ 8 6∼8 性质 1 2 9 ∼ 11 9∼11 性质 1 12 ∼ 13 12∼13 性质 2 14 ∼ 15 14∼15 性质 4 16 ∼ 17 16∼17 性质 5 18 ∼ 20 18∼20 无特殊性质 “性质 1”为：保证所有的地址串均符合规范； “性质 2”为：保证对于任意两台不同的计算机，如果它们同为服务机或者同为客户机，则它们提供的地址串一定不同； “性质 3”为：保证任意一台服务机的编号都小于所有的客户机； “性质 4”为：保证所有的地址串均形如 a.b.c.d:e 的格式，其中 � , � , � , � , � a,b,c,d,e 均为不超过 10 9 10 9 且不含有多余前导 0 0 的非负整数； “性质 5”为：保证所有的地址串均形如 a.b.c.d:e 的格式，其中 � , � , � , � , � a,b,c,d,e 均为只含有数字的非空字符串。

对于 100 % 100% 的数据，保证 1 ≤ � ≤ 1000 1≤n≤1000。

【提供 hack 数据感谢】

Unknown User 。 进入在线编程模式 (Alt+E) 递交 day20 关联结构 已认领 查看作业 成绩表 我的最近递交记录 帮助 状态正在进行…题目6开始时间2024-4-20 9:30截止时间2025-4-18 23:59可延期24 小时 状态 评测队列 服务状态 开发 开源 API 支持 帮助 QQ 群