【TCP】传输控制协议

图片

前言

TCP(Transmission Control Protocol)即传输控制协议,是一种面向连接的、可靠的、基于字节流的传输层通信协议。它由IETF的RFC 793定义,为互联网中的数据通信提供了稳定的传输机制。TCP在不可靠的IP层之上实现了数据传输的可靠性,通过使用确认、重传和错误检测等技术来确保数据的正确到达。

TCP的特点:

  1. 面向连接:TCP在数据传输之前需要建立连接,通信结束后会断开连接。

  2. 可靠传输:TCP确保数据包正确无误地从源点传送到目的地,若数据包在传输过程中丢失或出错,会被重新发送。

  3. 全双工通信:TCP允许数据在两个方向上同时传输,提高了通信效率。

  4. 流量控制:TCP通过滑动窗口机制进行流量控制,避免快速发送方压倒慢速接收方。

  5. 拥塞控制:TCP实施拥塞控制策略来避免网络拥塞,如慢启动、拥塞避免、快速重传和快速恢复等。

  6. 有序传输:TCP保证数据按发送时的顺序到达接收端。

  7. 可变大小的滑动窗口:TCP使用可变大小的滑动窗口来动态调整数据传输速率。

TCP 面向连接

TCP的面向连接特性确保了数据传输的稳定性和可靠性。具体如下:

  • 三次握手建立连接:在数据传输开始之前,TCP通过所谓的“三次握手”机制来建立一个连接。这个过程包括一个SYN(同步)信号的交换,以及确认信号ACK(应答),从而确保双方都准备好进行通信。

  • 一对一通信:一旦建立了连接,TCP就会在这个连接上进行一对一的数据交换。这意味着发送方和接收方之间建立了一条虚拟的、直接的通道,数据包会按照发送顺序到达对方。

  • 四次挥手断开连接:当数据传输完成后,TCP使用“四次挥手”过程来有序地关闭连接。这个过程涉及到FIN(结束)信号的交换和相应的ACK信号,确保双方都同意关闭连接,并且所有数据都已经传输完毕。

  • 可靠性保障:面向连接的特性还意味着TCP能够保证数据的可靠传输。它通过序列号、确认应答、重传机制等来确保每个数据包都能够正确地到达目的地,即使在网络条件不理想的情况下也能保持数据的完整性。

  • 流量控制和拥塞控制:TCP的面向连接特性还包括了流量控制和拥塞控制机制。这些机制帮助TCP适应网络的变化,避免因为数据发送过快而导致的网络拥塞或者接收方处理不过来的情况。

TCP的面向连接特性为网络通信提供了一种稳定可靠的方式,它通过建立和维护一个持续的连接状态,确保了数据的按序到达和完整性,同时也支持了复杂的流量控制和拥塞控制算法,以适应不断变化的网络环境。

TCP 可靠传输

TCP的可靠传输机制是其核心特性之一,确保了数据在网络中的完整性和顺序性。以下是TCP实现可靠传输的几个关键方法:

  • 检验和:TCP在发送数据时会计算检验和,并将其附加到数据包中。接收方在收到数据包后会重新计算检验和并与数据包中的检验和进行比对,以此来检测数据在传输过程中是否出现了错误。

  • 序列号/确认应答:TCP为每个数据包分配一个序列号,接收方在收到数据包后会发送一个确认应答,其中包含了期望收到的下一个序列号。这样发送方就可以知道哪些数据包已经被成功接收。

  • 超时重传:如果在规定的时间内没有收到确认应答,发送方会认为数据包丢失并重新发送。这个超时时间是通过自适应算法来确定的,以适应不同的网络条件。

  • 滑动窗口控制:TCP使用滑动窗口机制来进行流量控制,避免发送方发送的数据量超过接收方的处理能力。窗口的大小可以根据网络状况动态调整。

  • 拥塞控制:当网络出现拥塞时,TCP会减少数据的发送速率,以防止网络拥塞的进一步恶化。拥塞控制算法会根据网络的反馈信息来调整发送速率。

此外,TCP通过这些机制确保了即使在不可靠的IP网络上也能实现数据的可靠传输。它通过建立和维护一个持续的连接状态,确保了数据的按序到达和完整性,同时也支持了复杂的流量控制和拥塞控制算法,以适应不断变化的网络环境。

TCP 全双工通信

TCP的全双工通信指的是在同一连接中,两端设备都能够同时发送和接收数据。

首先,在全双工通信模式下,数据传输可以在两个方向上同时进行,而不需要等待对方回应。这意味着一个设备在发送数据的同时,也能够接收对方发送过来的数据。这种模式显著提高了通信的效率,因为它避免了半双工通信中必须等待一方完成发送后另一方才能开始发送的延迟。

其次,TCP协议通过其设计确保了这种全双工通信的实现。例如,TCP的报文段(Segment)包含了序列号和确认号等信息,使得设备可以连续发送数据并独立地确认收到的数据。此外,TCP的滑动窗口机制也支持全双工通信,允许每个方向上的流量控制独立于对方。

最后,TCP的这种双向通信能力是通过建立持久的连接来实现的,这个连接在数据交换完成之前一直保持活跃状态。即使在没有数据发送的时候,连接也不被关闭,从而允许任何一方在任何时间发送数据。

TCP的全双工通信为网络应用提供了高效、可靠的双向数据传输能力,它是TCP协议能够广泛应用的重要原因之一。

TCP 流量控制

TCP的流量控制是通过滑动窗口机制来实现的,它的目的是防止数据包丢失并确保网络资源的有效利用。

TCP流量控制的核心在于调节数据传输的速度,以确保发送方不会过快地发送数据以至于接收方无法及时处理。这种控制机制主要通过以下方式实现:

滑动窗口机制:TCP使用滑动窗口来控制数据的流动。窗口的大小表示了接收方能够接收的数据量。发送方会根据这个窗口的大小来调整自己的发送速率,确保不会超出接收方的处理能力。

窗口大小动态调整:接收方根据自身的接收缓存空间和处理能力,动态地调整窗口的大小,并通过TCP报文段中的窗口字段告知发送方。这样,发送方就可以根据最新的窗口大小来发送数据,避免过多的数据导致接收方缓冲区溢出。

避免分组丢失:流量控制的最终目的是为了避免分组丢失。如果发送方发送数据过快,超出了网络的传输能力或者接收方的处理速度,就可能导致数据包在网络中丢失。通过流量控制,可以确保数据包的顺利传输,减少重传的需要,提高网络的效率。

此外,在实际的网络环境中,由于各种因素的影响,如网络延迟、带宽变化等,TCP的流量控制机制需要不断地适应这些变化,以保持最佳的传输效率。例如,当网络拥塞时,TCP会减小窗口大小以降低发送速率,而当网络状况好转时,则会增大窗口大小以提高传输效率。

TCP的流量控制是一个复杂的过程,它涉及到多个参数和算法的相互作用。理解这些机制对于网络工程师来说非常重要,因为它们直接影响到网络应用的性能和用户体验。

TCP 拥塞控制

TCP拥塞控制是一个复杂的过程,它涉及到多个参数和算法的相互作用。

TCP拥塞控制是传输控制协议(TCP)中的一个重要机制,用于避免网络拥塞,确保数据能够有效、稳定地在互联网中传输。它通过监测网络状态并相应地调整数据的发送速率来实现这一目标。以下是TCP拥塞控制的关键点:

  • 拥塞窗口(CongWin):TCP连接的每一端都会维护一个拥塞窗口,这个窗口的大小表示在没有收到确认的情况下发送方可以发送的最大数据量。拥塞窗口的大小会根据网络的实时状态动态调整。

  • 慢启动和拥塞避免:当建立新的TCP连接时,TCP会经历一个慢启动阶段,初始时拥塞窗口设置为一个较小的值,然后逐渐增大。当拥塞窗口达到一定阈值后,进入拥塞避免阶段,增长速度会减慢。这样做的目的是为了避免一开始就发送大量数据导致网络拥塞。

  • 快速重传和快速恢复:如果发送方长时间未收到ACK而发生数据重传,这通常意味着网络可能出现了拥塞。此时,发送方会缩小拥塞窗口,降低发送速度。而当收到有效的ACK时,则会增大拥塞窗口,提高发送速度,因为这通常表示网络状态良好。

  • 拥塞控制策略:TCP拥塞控制的策略包括端到端拥塞控制和网络辅助的拥塞控制。端到端拥塞控制是由发送端自己来判断网络是否拥塞,并相应调整传输速率。而网络辅助的拥塞控制则是由网络中的路由器来告知发送方网络的拥塞情况。

TCP拥塞控制的目标是在保证数据传输效率的同时,避免因网络拥塞导致的数据传输问题。理解这些机制对于网络工程师来说非常重要,因为它们直接影响到网络应用的性能和用户体验。

TCP 有序传输

TCP的有序传输确保了数据包按照发送顺序到达接收方,从而保证了数据传输的可靠性和完整性。

  • 首先,在TCP协议中,每个数据包都被分配了一个序列号,这个序列号是连续的,确保了即使在网络中数据包经过了不同的路径,也能被正确地重新排序。这一点对于保证数据的有序性至关重要,因为网络层的协议如IP并不保证数据包的顺序。

  • 其次,TCP使用确认应答机制来确认数据包的接收。当接收方收到数据包时,它会发送一个包含期望收到的下一个序列号的ACK(确认应答信号),这允许发送方知道哪些数据已经被成功接收,并且可以按序处理后续的数据包。

  • 最后,如果数据包在传输过程中丢失,TCP会使用重传机制来重新发送这些数据包。这个机制确保了即使数据包丢失,也能够被重新发送并最终按顺序到达接收方。

总的来说,TCP的有序传输是通过序列号、确认应答和重传机制共同作用的结果,这些机制确保了数据包不仅能够到达目的地,而且能够按照发送时的顺序到达,从而为应用层提供了可靠的数据传输服务。理解这些机制对于网络工程师来说非常重要,因为它们直接影响到网络应用的性能和用户体验。

TCP 超时重传

TCP的超时重传机制是一种确保数据可靠性的关键特性,它通过在发送方设定一个定时器来监测数据的传输状态。

当发送方发送数据包后,会等待接收方返回确认报文(ACK)。如果在一定时间内未收到确认,发送方会认为数据包可能已经丢失或损坏,此时就会触发重传机制。这个时间阈值被称为重传超时(RTO),它会动态地根据网络状况进行调整。

RTO的计算通常基于往返时间(RTT)的估计,这是一个数据包从发送方到接收方再返回发送方所需的时间。为了更准确地计算RTO,TCP采用了如Karn算法等方法来避免不必要的重传并优化性能。此外,TCP还实现了快速重传机制,当发送方连续收到三个重复的ACK时,它会立即重传相应的数据包,而不是等待超时。

总的来说,TCP的超时重传机制是一个复杂的过程,它涉及到多个参数和算法的相互作用。理解这些机制对于网络工程师来说非常重要,因为它们直接影响到网络应用的性能和用户体验。

TCP 报文

TCP报文是TCP协议在传输数据时所使用的数据单元。

图片

首先,TCP报文包括一个TCP头部和紧随其后的数据部分。TCP头部包含了多个字段,每个字段都有特定的作用,共同确保了TCP的可靠传输和流量控制。以下是TCP报文的主要组成部分:

  • 源端口(Source Port):源计算机上的应用程序的端口号;

  • 目的端口(Destination Port):目标计算机的应用程序端口号;

  • 序列号(Sequence Number):它表示本报文段所发送数据的第一个字节的编号。在 TCP 连接中,所传送的字节流的每一个字节都会按顺序编号。当SYN标记不为1时,这是当前数据分段第一个字母的序列号;如果SYN的值是1时,这个字段的值就是初始序列值(ISN),用于对序列号进行同步。这时,第一个字节的序列号比这个字段的值大1,也就是ISN加1;

  • 确认号(Acknowledgment Number,ACK Number):它表示接收方期望收到发送方下一个报文段的第一个字节数据的编号(下一个序列号),等于已经接收确认的数据序列号加1,也就是接收方收到的序列号+报文大小+1;

  • 数据偏移(Header Length):数据偏移是指数据段中的“数据”部分起始处距离 TCP 数据段起始处的字节偏移量,占 4 位。其实这里的“数据偏移”也是在确定 TCP 数据段头部分的长度,告诉接收端的应用程序,数据从何处开始;

  • 保留位(Reserved):占 4 位。为 TCP 将来的发展预留空间,目前必须全部为 0;

  • 标志位字段:

    • CWR(Congestion Window Reduce):拥塞窗口减少标志,用来表明它接收到了设置 ECE 标志的 TCP 包。并且,发送方收到消息之后,通过减小发送窗口的大小来降低发送速率。

    • ECE(ECN Echo):用来在 TCP 三次握手时表明一个 TCP 端是具备 ECN 功能的。在数据传输过程中,它也用来表明接收到的 TCP 包的 IP 头部的 ECN 被设置为 11,即网络线路拥堵。

    • URG(Urgent):表示本报文段中发送的数据是否包含紧急数据。URG=1 时表示有紧急数据。当 URG=1 时,后面的紧急指针字段才有效。

    • ACK:表示前面的确认号字段是否有效。ACK=1 时表示有效。只有当 ACK=1 时,前面的确认号字段才有效。TCP 规定,连接建立后,ACK 必须为 1。

    • PSH(Push):告诉对方收到该报文段后是否立即把数据推送给上层。如果值为 1,表示应当立即把数据提交给上层,而不是缓存起来。

    • RST:表示是否重置连接。如果 RST=1,说明 TCP 连接出现了严重错误(如主机崩溃),必须释放连接,然后再重新建立连接。

    • SYN:在建立连接时使用,用来同步序号。当 SYN=1,ACK=0 时,表示这是一个请求建立连接的报文段;当 SYN=1,ACK=1 时,表示对方同意建立连接。SYN=1 时,说明这是一个请求建立连接或同意建立连接的报文。只有在前两次握手中 SYN 才为 1。

    • FIN:标记数据是否发送完毕。如果 FIN=1,表示数据已经发送完成,可以释放连接。

  • 滑动窗口(Window Size):占 16 位。它表示从 Ack Number 开始还可以接收多少字节的数据量,也表示当前接收端的接收窗口还有多少剩余空间。该字段可以用于 TCP 的流量控制;

  • 校验和(TCP Checksum):它用于确认传输的数据是否有损坏。发送端基于数据内容校验生成一个数值,接收端根据接收的数据校验生成一个值。两个值必须相同,才能证明数据是有效的。如果两个值不同,则丢掉这个数据包。Checksum 是根据伪头 + TCP 头 + TCP 数据三部分进行计算的;

  • 紧急指针(Urgent Pointer):仅当前面的 URG 控制位为 1 时才有意义。它指出本数据段中为紧急数据的字节数,占 16 位。当所有紧急数据处理完后,TCP 就会告诉应用程序恢复到正常操作。即使当前窗口大小为 0,也是可以发送紧急数据的,因为紧急数据无须缓存;

  • 选项(Option):长度不定,但长度必须是 32bits 的整数倍。

TCP报文可能还包含选项字段,用于提供额外的功能,如窗口规模、最大报文段长度等。这些选项可以增强TCP的性能和灵活性。

总的来说,TCP报文的设计体现了TCP协议的核心特性,即面向连接、可靠的字节流服务。通过这些精心设计的字段,TCP能够实现数据的可靠传输,适应不同的网络条件和应用需求。

TCP 协议的例子

TCP协议是一种面向连接的、可靠的、基于字节流的传输层通信协议。在Java中,可以使用java.net包中的Socket和ServerSocket类来实现TCP协议的客户端和服务端通信。 以下是一个简单的Java TCP客户端和服务端的示例代码:

服务端代码:

import java.io.*;
import java.net.*;

public class TCPServer {
    public static void main(String[] args) throws IOException {
        // 创建一个ServerSocket对象,监听8080端口
        ServerSocket serverSocket = new ServerSocket(8080);
        System.out.println("服务器启动,等待客户端连接...");

        // 调用accept()方法等待客户端连接
        Socket socket = serverSocket.accept();
        System.out.println("客户端已连接,IP地址:" + socket.getInetAddress().getHostAddress());

        // 获取输入流,读取客户端发送的数据
        BufferedReader in = new BufferedReader(new InputStreamReader(socket.getInputStream()));
        String msg = in.readLine();
        System.out.println("收到客户端消息:" + msg);

        // 获取输出流,向客户端发送数据
        PrintWriter out = new PrintWriter(socket.getOutputStream(), true);
        out.println("你好,客户端!");

        // 关闭资源
        out.close();
        in.close();
        socket.close();
        serverSocket.close();
    }
}

客户端代码:

import java.io.*;
import java.net.*;

public class TCPClient {
    public static void main(String[] args) throws IOException {
        // 创建一个Socket对象,连接到服务器
        Socket socket = new Socket("localhost", 8080);
        System.out.println("客户端已启动,连接到服务器...");

        // 获取输出流,向服务器发送数据
        PrintWriter out = new PrintWriter(socket.getOutputStream(), true);
        out.println("你好,服务器!");

        // 获取输入流,读取服务器发送的数据
        BufferedReader in = new BufferedReader(new InputStreamReader(socket.getInputStream()));
        String msg = in.readLine();
        System.out.println("收到服务器消息:" + msg);

        // 关闭资源
        out.close();
        in.close();
        socket.close();
    }
}

在这个示例中,服务端监听8080端口,等待客户端连接。客户端连接到服务端后,双方可以通过输入输出流进行数据的发送和接收。

结语

TCP作为互联网协议族的核心组成部分之一,其设计精妙且功能强大,为全球范围内的数据通信提供了稳定可靠的基础。尽管随着时间的推移,新的技术和协议不断涌现,但TCP依然是许多网络应用的首选传输协议。了解和掌握TCP的原理及其工作机制对于网络工程师、开发者乃至任何对计算机网络感兴趣的人都是至关重要的。随着网络环境的不断变化,对TCP的优化和改进也将持续进行,以满足日益增长的网络通信需求。

图片

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/348869.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

HCIE之BGP正则表达式(四)

BGP 一、AS-Path正则表达式数字| 等同于或的关系[]和.$ 一个字符串的结束_代表任意^一个字符串的开始()括号包围的是一个组合\ 转义字符* 零个或多个?零个或一个一个或多个 二、BGP对等体组 一、AS-Path正则表达式 正则表达式是按照一定模版匹配字符串的公式 AR3上…

数字孪生系统的难点

数字孪生系统的开发和实施涉及一些技术难点,这些难点需要综合应用多个领域的知识和技术来克服。以下是一些数字孪生系统开发中的技术难点,希望对大家有所帮助。北京木奇移动技术有限公司,专业的软件外包开发公司,欢迎交流合作。 1…

React进阶 - 14(说一说”虚拟DOM“中的”Diff算法“)

本章内容 目录 一、了解 Diff 算法二、key 值的重要性三、为什么不建议使用 index 做 key 值 上一节我们初步了解了 React中的”虚拟 DOM“ ,本节我们来说一说”虚拟DOM“中的”Diff算法“ 一、了解 Diff 算法 在上一篇中,我们有讲到:当 st…

CentOS 6/7/8系统加固方案

密码失效时间 设置密码失效时间,强制定期修改密码,减少密码被泄漏和猜测风险,若使用非密码登陆方式(如密钥对)请忽略此项。 在 /etc/login.defs 中将 PASS_MAX_DAYS 参数设置为 60-180之间,如: PASS_MAX_DAYS 180 需同时执行命令设置root密码失效时间: chage --maxdays…

编程笔记 html5cssjs 057 CSS导航栏

编程笔记 html5&css&js 057 CSS导航栏 一、导航栏 链接列表二、垂直导航栏三、水平导航栏四、下拉菜单五、实例: 响应式导航栏小结 导航栏。易用的导航对于任何网站都很重要。通过使用 CSS,您可以将无聊的 HTML 菜单转换为美观的导航栏。 一、导航栏 链接…

C语言实现归并排序算法(附带源代码)

归并排序 把数据分为两段,从两段中逐个选最小的元素移入新数据段的末尾。 可从上到下或从下到上进行。 动态效果过程演示: 归并排序(Merge Sort)是一种分治算法,它将一个数组分为两个子数组,分别对这两个…

【linux】Debian防火墙

Debian系统默认没有安装防火墙,但用户可以根据需要自行选择并安装一个防火墙以增强系统安全性。 一、查看Debian 桌面系统的防火墙是否关闭 在Debian及其他基于Linux的桌面系统中,防火墙功能通常是由iptables或nftables规则集控制的,而ufw&…

金蝶云星空 ServiceGateway RCE漏洞复现

0x01 产品简介 金蝶云星空是一款云端企业资源管理(ERP)软件,为企业提供财务管理、供应链管理以及业务流程管理等一体化解决方案。金蝶云星空聚焦多组织,多利润中心的大中型企业,以 “开放、标准、社交”三大特性为数字经济时代的企业提供开放的 ERP 云平台。服务涵盖:财…

burp靶场--CSRF

burp靶场–CSRF https://portswigger.net/web-security/csrf#what-is-csrf ### 什么是 CSRF? 跨站请求伪造(也称为 CSRF)是一种 Web 安全漏洞,允许攻击者诱导用户执行他们不打算执行的操作。它允许攻击者部分规避同源策略&#…

【Python】采用OpenCV和Flask来进行网络图像推流的低延迟高刷FPS方法(项目模板)

【Python】采用OpenCV和Flask来进行网络图像推流的低延迟高刷FPS方法(项目模板) gitee项目模板: 网络图像推流项目模板(采用OpenCV和Flask来进行网络图像推流的低延迟高刷FPS方法) 前文: 【最简改进】基于…

短剧小程序开发:打造全新用户体验

随着移动互联网的普及,小程序作为一种轻量级的应用程序形式,已经成为了现代人生活中不可或缺的一部分。短剧小程序作为其中的一种,更是以其独特的魅力,吸引了大量用户。本文将探讨短剧小程序的发展背景、优势、开发流程和未来趋势…

【java面试】常见问题(超详细)

目录 一、java常见问题JDK和JRE的区别是什么?Java中的String类是可变的还是不可变的?Java中的equals方法和hashCode方法有什么关系?Java中什么是重载【Overloading】?什么是覆盖【Overriding】?它们有什么区别&#xf…

Beego之Beego MVC架构介绍

1、beego MVC架构介绍 beego 是一个典型的 MVC 框架,它的整个执行逻辑如下图所示: 通过文字来描述如下: 1、在监听的端口接收数据,默认监听在 8080 端口。 2、用户请求到达 8080 端口之后进入 beego 的处理逻辑。 3、初始化 C…

【每日一题】4.LeetCode——杨辉三角

📚博客主页:爱敲代码的小杨. ✨专栏:《Java SE语法》 ❤️感谢大家点赞👍🏻收藏⭐评论✍🏻,您的三连就是我持续更新的动力❤️ 🙏小杨水平有限,欢迎各位大佬指点&…

idea连接docker

idea 插件无法连接docker问题 原文:idea 插件无法连接docker问题 // 修改docker配置 vi /usr/lib/systemd/system/docker.service // 加上该段配置允许任何ip访问 -H tcp://0.0.0.0:2375 -H unix://var/run/docker.sock // 重启docker即可 systemctl restart dock…

图像处理------调整色调

什么是色调? 色调,在画面上表现思想、感情所使用的色彩和色彩的浓淡。分为暖色调和冷色调。 from cv2 import destroyAllWindows, imread, imshow, waitKey#创建棕褐色色调 def make_sepia(img, factor: int):pixel_h, pixel_v img.shape[0], img.shap…

OSPF协议解析及相关技术探索(C/C++代码实现)

OSPF(开放最短路径优先)是一种用于自治系统(AS)内部的路由协议,它是基于链路状态算法的。OSPF的设计目的是为了提供一种可扩展、快速收敛和高效的路由解决方案。 OSPF概念和特点 概念 自治系统(AS&#…

二叉树的最大深度[简单]

优质博文:IT-BLOG-CN 一、题目 给定一个二叉树root,返回其最大深度。 二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1: 输入:root [3,9,20,null,null,15,7] 输出:3 示例 2&#xff1a…

高水平 ICT 实验实训平台建设

一、平台建设概述 1.1 人工智能仿真实验实训平台 建设高水平 ICT 实验实训平台–人工智能仿真实验实训平台,是为了提供学生在人工智能领域深入学习和实践的机会。承载《人工智能基础》《人工智能应用》《移动机器人技术应用》《视觉开源机器人》《深度学习与神经网…

C. Doremy‘s City Construction(二分图问题)

思路&#xff1a;把集合划分成两部分,一部分中每个数都比另一部分小,这两部分连成一个完全二分图,这种情况是最优的,还需要特判所有数都相等的情况. 代码&#xff1a; void solve(){int n;cin >> n;vector<int>a(n 1);for(int i 1;i < n;i )cin >> a[…