点击打开链接
题目意思:给定n个节点,(n<=8),节点的编号为A~Z 来表示,要求找到一个节点的序列,使得该序列最大的节点的Bandwidth为所有序列中的最小值,(节点的Bandwidth是指和它所连接的点中和它距离最大的值)。
解题思路:由于最多只有8个节点,那么可以枚举这个解空间的所有情况,然后找到其中的最有解并且记录下它的节点顺序,那么我们可以通过求全排列的方法去一一枚举这些排列
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <algorithm>
using namespace std;
const int MAXN = 100000;
int k, cur, ans;
int vis[8];//存储节点的编号,通过编号来映射节点
int mark[30][30]; //用来标记节点和哪些节点有连接
int Minsum[MAXN][8];//用来记录每一个排列的节点的顺序
int Min;
//计算最小值的函数
void Minfun() {
int tempmax[8];//临时存储每一个点的最大值
int T, Tmax = 0;//T存储当前节点和另外节点的距离,Tmax存储一个点中的最大距离(后面求一个排列的最大值)
memset(tempmax, 0, sizeof (tempmax)); //初始话为0
for (int i = 0; i < k; i++) {//枚举这个序列的点
Tmax = 0;
for (int j = 1; j <= 26; j++) {
if (mark[vis[i]][j]) {//找打一个点的匹配点的最大的值
for (int t = 0; t < k; t++) {//找匹配点的位置
if (j == vis[t]) {
T = abs(i - t); //找到位置的距离
break;
}
}
if (Tmax < T)
Tmax = T;
}
}
tempmax[i] = Tmax;
}
Tmax = 0;
for (int i = 0; i < k; i++) {//求出该种排列的最大值
if (Tmax < tempmax[i]) {
Tmax = tempmax[i];
}
}
if (Min > Tmax) {//更新Min的值
ans = cur;//记录位置
Min = Tmax;
}
}
//处理函数
void solve() {
Min = 100000000;
cur = 0;
for (int i = 0; i < k; i++)//必须先保存到Minsum[0]里,不然调用了next_permutation(vis, vis + k)将直接跳到下一个排列
Minsum[0][i] = vis[i];
Minfun();//求出Min
++cur;
while (next_permutation(vis, vis + k)) {//得到全排列
for (int i = 0; i < k; i++)
Minsum[cur][i] = vis[i]; //把序列存入mark数组里面
Minfun();//判断是否最小值
cur++;
}
}
//输出函数
void output() {
for (int i = 0; i < k; i++)
printf("%c ", Minsum[ans][i] + 64);
printf("-> %d\n", Min);
}
//主函数
int main() {
int i, j;
char c;
int Tvis[27];
string str;
while (cin >> c) {
if (c == '#')
break;
memset(mark, 0, sizeof (mark));
memset(Tvis, 0, sizeof (Tvis));
memset(Minsum, 0, sizeof (Minsum));
i = c - 64;
vis[0] = i;
Tvis[i] = 1;
k = 1;
cin >> str;
//处理字符串
for (j = 0; j < str.size(); ++j) {
if (str[j] == ':') {
continue;
}
if (str[j] == ';') {
++j;
i = str[j] - 64;
if (isupper(str[j])) {
if (Tvis[str[j] - 64] == 0) {
Tvis[str[j] - 64] = 1;
vis[k] = str[j] - 64;
++k;
}
}
continue;
}
if (isupper(str[j])) {
if (Tvis[str[j] - 64] == 0) {
Tvis[str[j] - 64] = 1;
vis[k] = str[j] - 64;
++k;
}
}
mark[i][str[j] - 64] = 1;//标记为1,说明两个节点有连接
}
sort(vis, vis + k); //必须先对数组先排序
solve();
output();
}
}
分享到:
相关推荐
A State-Space Technique for Ultrawide-Bandwidth Coherent Processing
高带宽内存接口pdf
Laravel开发-laravel-bandwidth 用于与带宽API交互的简单Laravel接口。
clumsy-bandwidth-win64:在Windows下,模拟网络环境(丢包,延迟,带宽)的软件,亲测可用
安装SDK node-bandwidth在NPM上可用: npm install --save node-bandwidth 支持的版本node-bandwidth应该在6.0.0所有版本的节点上都可以使用。 但是,由于Node和npm环境的快速发展,我们只能在LTS版本的Node上...
This paper describes a new control algorithm which can enhance the dynamics of a ... the bandwidth of the current controller was enhanced up to 250 Hz, and that of the speed controller was up to 50 Hz.
High-bandwidth Digital Content Protection (HDCP) is a form of digital copy protection developed by Intel Corporation [1] to prevent copying of digital audio and video content as it travels across ...
ADSL-Bandwidth,不错的小工具
KEYSIGHT_DCA Wide-Bandwidth Oscilloscope Family.pdf
set -g @plugin 'xamut/tmux-network-bandwidth' 按prefix + I提取插件并获取其源代码。 完毕。 手动的 在某个地方克隆仓库。 在.tmux.conf添加run-shell : run-shell PATH_TO_REPO/tmux-network-bandwidth.tmux...
具体讲解了相干带宽和相干时间 内容和原理,让我们更容易理解衰落信道。
pip install bandwidth-sdk 用法 客户初始化 import bandwidth voice_api = bandwidth . client ( 'voice' , 'u-user' , 't-token' , 's-secret' ) messaging_api = bandwidth . client ( 'messaging' , 'u-user' ,...
IP网络远程镜像系统中的带宽精简装置,谭乐娟,姚文斌,IP网络远程镜像系统在灾备系统中得到了广泛应用。本文在IP网络远程镜像系统中设计并实现了带宽精简装置。在该装置中,本文提出了��
<artifactId>bandwidth-java-iris-sdk <version>1.0 <scope>compile 如果你想自己编译它,方法如下: $ git clone git@github.com:bandwidthcom/java-bandwidth-iris.git $ cd java-bandwidth-iris $ mvn install ...
带宽Go SDK 注意:从2019年4月开始,低于1.0.0的go-bandwidth版本将与Bandwidth的V2消息传递不兼容。 如果您正在使用Bandwidth的V2消息传递,则需要将go-bandwidth软件包版本更新为1.0.0或更高版本。 如果您不使用...
注意:自2019年4月起,小于4.0.0的csharp-bandwidth版本将与Bandwidth的V2消息传递不兼容。 如果您使用带宽的V2消息传递,则需要将csharp-bandwidth软件包版本更新为4.0.0或更高版本。 如果您不使用带宽的V2消息...
High-bandwidth Digital Content Protection System Revision 1.4 8 July, 2009
收集网络带宽使用情况 收集了用于监视网络带宽使用... Exec username " /path/to/exec-network-bandwidth-usage.sh " " your-network-interface-name " < /Plugin > 重启收集: service collectd restart 屏幕截图
tpg-bandwidth是一个易于使用的实用程序,它返回TPG Australia连接的当前带宽使用情况和可用带宽。 将来,它将包括一个可刷新的图形界面,并支持帐户监视(信用等)。
An all-fiberized and narrow-bandwidth master oscillator power amplification (MOPA) system with record output power of 4 kW level and slope efficiency of 78% is demonstrated. Tandem pumping strategy is...