鏈接：https://www.nowcoder.com/acm/contest/93/F
來源：牛客網(wǎng)

題目描述

你們wyh學(xué)長給你n個(gè)點(diǎn)，讓你分成2個(gè)集合，然后讓你將這n個(gè)點(diǎn)進(jìn)行兩兩連接在一起，連接規(guī)則是這樣的

1.?連接的兩個(gè)點(diǎn)必須在不同的兩個(gè)集合

2.?一個(gè)集合內(nèi)部任意兩個(gè)點(diǎn)之間不能相連

現(xiàn)在，wyh學(xué)長需要讓你將這n個(gè)點(diǎn)任意分成2個(gè)集合之后，最多能連接多少條邊？

輸入描述:

輸入第一行一個(gè)整數(shù)T(1<=T<=100000)
接下來T組測(cè)試數(shù)據(jù)，每組測(cè)試數(shù)據(jù)輸入一個(gè)整數(shù)n(1<=n<=100000)

輸出描述:

對(duì)于每組測(cè)試數(shù)據(jù)，輸出對(duì)應(yīng)答案 示例1

輸入

4 0 1 2 4

輸出

0 0 1 4

說明

對(duì)于4的情況，設(shè)4個(gè)點(diǎn)為A,B,C,D
第一個(gè)集合元素為 A,B
第二個(gè)集合元素為C,D
連接的邊為AC,AD,BC,BD
此時(shí)為最大情況，所以答案為4
【分析】：開始以為是二分圖匹配，畫了畫發(fā)現(xiàn)直接當(dāng)兩邊最接近的時(shí)候最大，兩邊數(shù)量要么相等，要么相差1
【代碼】： #include<bits/stdc++.h>using namespace std;#define ll long longint main() {int t;ll n;cin>>t;while(t--){ll ans;cin>>n;ll a = n / 2;ll b = n - a;cout<<a * b<<endl; //注意相乘用long long} }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Roni-i/p/8724855.html

總結(jié)

以上是生活随笔為你收集整理的2018年东北农业大学春季校赛 F wyh的集合【思维】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。