资本运动 |竞争性编程
Capital Movement | Competitive Programming
问题
假设一个国家有'n'个城市,其中一个是首都。所有城市都通过 'n-1' 条道路相连,可以使用这些道路在任意两个城市之间旅行。问题中提供了城市人口Pi。
现在,如果一个城市感染了病毒,那么与该城市相连的城市也会被感染。在感染的情况下,会选择一个新首都。人口最多的未感染城市成为新首都。
输入
输入的第一行包含一个整数T,表示测试用例的数量。下面是T个测试用例的描述。
每个测试用例的第一行包含一个整数N,表示城市数。
下一行包含N个space-分隔的整数P1,P2,...,PN表示每个城市的人口。
接下来的 N-1 行包含两个 space 分隔的整数,每个 V 和 U 表示城市 V 和 U 之间有一条路。
输出
对于每个测试用例,输出包含 N 个整数 A1、A2、...、AN 的单行,用 space 分隔。这里 Ai 表示在感染开始从城市 i 传播的情况下被选为新首都的城市的数量。如果感染影响所有城市输出 0.
例子
输入:
1
6
5 10 15 20 25 30
1 3
2 3
3 4
4 5
4 6
输出:
6 6 6 2 6 5
我的 C++ 解决方案
#include <iostream>
#include <vector>
#include <list>
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
int t;
scanf("%d", &t); //No. of test cases
while(t--) {
int n;
scanf("%d", &n);
vector<int> p(n); //vector for storing population of each city
for(int i = 0; i < n; i++)
scanf("%d", &p[i]);
vector<list<int> > graph(n); //vector of lists for storing connection between cities
for(int i = 0; i < n-1; i++) {
int a, b;
scanf("%d %d", &a, &b);
graph[--a].push_back(--b);
graph[b].push_back(a);
}
for(int i = 0; i < n; i++) {
vector<int> temp = p; //Temporary vector
/*All the infected cities are assigned a population
of -1 so that they don't compete to become the largest capital*/
temp[i] = -1;
if(graph[i].size() == n-1) {//Printing "0" if all cities have connection with the infected city.
cout<<"0 ";
continue;
}
int s = graph[i].size();
for(int j = 0; j < s; j++) {
temp[graph[i].front()] = -1;
graph[i].pop_front();
}
/*Finding max. population*/
int maxindex = std::distance(temp.begin(), std::max_element(temp.begin(), temp.end()));
printf("%d ", maxindex+1);
}
printf("\n");
}
return 0;
}
函数max_element 使时间复杂度变为二次方。
我的解决方案是让大量输入超出时间限制。因此,我的程序需要改进执行时间。请帮忙。谢谢你的时间。
因为没有关于 "bigger inputs" 是什么意思的信息,我猜它指的是拥有更多的城市。在这种情况下,您正在制作一个巨大的 (nxn) 图形数组,这将导致更多内存被占用,同时(大部分)是空的,因为只有 n-1 条道路。
考虑将城市与 std::list 连接起来,然后只查找与受感染城市不在同一列表中的城市。
已解决!诀窍是预先对城市人口进行排序。
#include <iostream>
#include <vector>
#include <list>
#include <stdio.h>
#include <algorithm>
using namespace std;
bool myfnc(pair<int, int> i, pair<int, int> j) {
return i.first > j.first;
}
int main() {
int t;
scanf("%d", &t);
while(t--) {
int n, d;
scanf("%d", &n);
vector<int> p(n);
int m = 0, mi = 0;
for(int i = 0; i < n; i++) {
scanf("%d", &d);
p[i] = d;
}
vector<pair<int, int> > p1(n);
for(int i = 0; i < n; i++) {
p1[i].first = p[i];
p1[i].second = i;
}
sort(p1.begin(), p1.end(), myfnc);
vector<vector<bool> > graph(n, vector<bool> (n));
for(int i = 0; i < n-1; i++) {
int a, b;
scanf("%d %d", &a, &b);
graph[--a][--b] = 1;
graph[b][a] = 1;
graph[i][i] = 1;
}
graph[n-1][n-1] = 1;
for(int i = 0; i < n; i++) {
int j;
for(j = 0; j < n; j++) {
if(graph[i][p1[j].second] == 0) {
printf("%d ", p1[j].second+1);
break;
}
}
if(j == n)
printf("0 ");
}
printf("\n");
}
return 0;
}
问题
假设一个国家有'n'个城市,其中一个是首都。所有城市都通过 'n-1' 条道路相连,可以使用这些道路在任意两个城市之间旅行。问题中提供了城市人口Pi。
现在,如果一个城市感染了病毒,那么与该城市相连的城市也会被感染。在感染的情况下,会选择一个新首都。人口最多的未感染城市成为新首都。
输入
输入的第一行包含一个整数T,表示测试用例的数量。下面是T个测试用例的描述。
每个测试用例的第一行包含一个整数N,表示城市数。
下一行包含N个space-分隔的整数P1,P2,...,PN表示每个城市的人口。
接下来的 N-1 行包含两个 space 分隔的整数,每个 V 和 U 表示城市 V 和 U 之间有一条路。
输出
对于每个测试用例,输出包含 N 个整数 A1、A2、...、AN 的单行,用 space 分隔。这里 Ai 表示在感染开始从城市 i 传播的情况下被选为新首都的城市的数量。如果感染影响所有城市输出 0.
例子
输入:
1
6
5 10 15 20 25 30
1 3
2 3
3 4
4 5
4 6
输出:
6 6 6 2 6 5
我的 C++ 解决方案
#include <iostream>
#include <vector>
#include <list>
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
int t;
scanf("%d", &t); //No. of test cases
while(t--) {
int n;
scanf("%d", &n);
vector<int> p(n); //vector for storing population of each city
for(int i = 0; i < n; i++)
scanf("%d", &p[i]);
vector<list<int> > graph(n); //vector of lists for storing connection between cities
for(int i = 0; i < n-1; i++) {
int a, b;
scanf("%d %d", &a, &b);
graph[--a].push_back(--b);
graph[b].push_back(a);
}
for(int i = 0; i < n; i++) {
vector<int> temp = p; //Temporary vector
/*All the infected cities are assigned a population
of -1 so that they don't compete to become the largest capital*/
temp[i] = -1;
if(graph[i].size() == n-1) {//Printing "0" if all cities have connection with the infected city.
cout<<"0 ";
continue;
}
int s = graph[i].size();
for(int j = 0; j < s; j++) {
temp[graph[i].front()] = -1;
graph[i].pop_front();
}
/*Finding max. population*/
int maxindex = std::distance(temp.begin(), std::max_element(temp.begin(), temp.end()));
printf("%d ", maxindex+1);
}
printf("\n");
}
return 0;
}
函数max_element 使时间复杂度变为二次方。 我的解决方案是让大量输入超出时间限制。因此,我的程序需要改进执行时间。请帮忙。谢谢你的时间。
因为没有关于 "bigger inputs" 是什么意思的信息,我猜它指的是拥有更多的城市。在这种情况下,您正在制作一个巨大的 (nxn) 图形数组,这将导致更多内存被占用,同时(大部分)是空的,因为只有 n-1 条道路。 考虑将城市与 std::list 连接起来,然后只查找与受感染城市不在同一列表中的城市。
已解决!诀窍是预先对城市人口进行排序。
#include <iostream>
#include <vector>
#include <list>
#include <stdio.h>
#include <algorithm>
using namespace std;
bool myfnc(pair<int, int> i, pair<int, int> j) {
return i.first > j.first;
}
int main() {
int t;
scanf("%d", &t);
while(t--) {
int n, d;
scanf("%d", &n);
vector<int> p(n);
int m = 0, mi = 0;
for(int i = 0; i < n; i++) {
scanf("%d", &d);
p[i] = d;
}
vector<pair<int, int> > p1(n);
for(int i = 0; i < n; i++) {
p1[i].first = p[i];
p1[i].second = i;
}
sort(p1.begin(), p1.end(), myfnc);
vector<vector<bool> > graph(n, vector<bool> (n));
for(int i = 0; i < n-1; i++) {
int a, b;
scanf("%d %d", &a, &b);
graph[--a][--b] = 1;
graph[b][a] = 1;
graph[i][i] = 1;
}
graph[n-1][n-1] = 1;
for(int i = 0; i < n; i++) {
int j;
for(j = 0; j < n; j++) {
if(graph[i][p1[j].second] == 0) {
printf("%d ", p1[j].second+1);
break;
}
}
if(j == n)
printf("0 ");
}
printf("\n");
}
return 0;
}