我该如何解决以下问题？ [英] How do I solve the following problem ?
问题描述
给定n个整数的数组C C1，C2，... Cn和n-1个整数对（p，q），它们代表p&之间的双向链接。 q。
我们的任务是找到每个索引i从1到n的数组C的索引j，使得Cj的值最大而j不是等于i并且在我们的整数对中也没有链接到i。输出将是n个空格分隔的整数。
此外，如果找不到j的j特别是我为那个输出0。
1< = n< = 50000
1< = Ci< = 10 ^ 9
所有Ci都是不同的
1< = p< = n
1< = q< = n
< b>输入格式： -
n
C1 C2 C3 ... Cn
pq
pq
。 。
。 。
n-1次
输出格式： -
A1 A2 A3 ...一个
其中，每个A包含对应i的整数j。
< b>样品输入： -
5
2 10 6 7 12
1 3
2 3
3 4
4 5
样品输出： -
5 5 5 2 2
时间限制： - 1秒
我尝试了什么：
我的代码适合小n喜欢1< = n< = 100但超过大n的时间限制，例如1< = n< = 50000.
这是我的代码： -
Given an array C of n integers C1, C2, ... Cn and n-1 pairs of integers (p,q) which represents bi-directional links between p & q.
Our task is to find for every index i from 1 to n the index j of the array C such that the value of Cj is largest and j is not equal to i and is also not linked to i in our pairs of integers.Output would be n space separated integers.
Also, if there is no j found for a particular i output 0 for that i.
1 <= n <= 50000
1 <= Ci <= 10^9
All Ci are distinct
1 <= p <= n
1 <= q <= n
Input Format :-
n
C1 C2 C3 ... Cn
p q
p q
. .
. .
n-1 times
Output format:-
A1 A2 A3 ... An
where, every A contains the integer j for corresponding i.
Sample Input :-
5
2 10 6 7 12
1 3
2 3
3 4
4 5
Sample Output :-
5 5 5 2 2
Time limit :- 1 sec
What I have tried:
My code works fine for small n like 1 <= n <= 100 but exceeds time limit for large n like 1 <= n <= 50000.
Here's my code :-
#include <stdio.h>
#include <math.h>
#define LL long long
typedef struct{
LL val;
int index;
}type1;
void merge(type1 A[], int l, int m, int r)
{
int n1 = m - l + 1, n2 = r - m, i, j, k;
type1 left[n1 + 1], right[n2 + 1];
for(i = 1; i <= n1; i++)
left[i] = A[l + i - 1];
for(i = 1; i <= n2; i++)
right[i] = A[m + i];
left[n1 + 1].val = INFINITY;
right[n2 + 1].val = INFINITY;
i = 1;
j = 1;
for(k = l; k <= r; k++)
{
if(left[i].val <= right[j].val)
{
A[k] = left[i];
i++;
}
else
{
A[k] = right[j];
j++;
}
}
}
void mergesort(type1 A[], int l, int r)
{
if(r > l)
{
int m = (l + r) / 2;
mergesort(A, l, m);
mergesort(A, m+1, r);
merge(A, l, m, r);
}
}
int main(void)
{
int t;
scanf("%d", &t);
while(t--)
{
int n, i, j, k, p, q;
scanf("%d", &n);
type1 C[n];
// Getting input for array C
for(i = 1; i <= n; i++){
scanf("%lld", &C[i].val);
C[i].index = i;
}
mergesort(C, 1, n);
// Declaring a 2D matrix for storing the links between p & q
int arr[n+1][n+1];
// Initializing arr[][] to 0
for(i = 0; i <= n; i++)
{
for(j = 0; j <= n; j++){
if(i == j)
arr[i][j] = 1;
else
arr[i][j] = 0;
}
}
// Getting input for our pairs of p & q and updating arr[][]
for(i = 0; i < n-1; i++)
{
scanf("%d %d", &p, &q);
arr[p][q] = 1;
arr[q][p] = 1;
}
// Declaring variable A to store the output
int A;
for(i = 1; i <= n; i++)
{
A = 0;
for(j = n; j > 0; j--)
{
k = C[j].index;
if(arr[k][i] == 0)
{
A = k;
break;
}
}
printf("%d ", A);
}
printf("\n");
}
return 0;
}
推荐答案
您已在您将如何解决以下问题？ [ ^ ]。请不要重新发布。
此外，没有人会为你做功课。
You already posted this question at How will you solve the following problem ?[^]. Please do not repost.
Also, no one is going to do your homework for you.
这不是正确的C代码，甚至不会编译。与上一篇文章中的问题相同：
This is no correct C code and won't even compile. Same problem as in your last post:
long long C[n];
不起作用，因为编译器无法为编译时未知的数量n分配空间。
doesn't work, because the compiler cannot allocate space for a quantity n that is unknown at compile time. Nor will
int arr[n+1][n+1];
因同样的原因而工作。所以首先修复它，你至少可以运行你的代码。
接下来你将不得不改进你的算法。目前，您正试图以蛮力的方式解决问题。这不会在给定的时限内起作用 - 这就是整个练习的内容。因此，开始寻找一种更聪明的方法来处理事情。
首先想到的是，只有一个节点具有最大值M.所有节点都没有链接到M将被分配M的索引。这就是为什么索引5在你的例子中出现三次。因此，确定最大节点并将其索引分配给除该节点本身之外的所有节点是合理的默认初始化。
接下来查找链接到最大节点的所有节点集节点M，我们称之为Mset。 （您的示例告诉我您将链接一词解释为非传递性，即只有在它们之间存在明确的链接条目时，A才链接到B.作为该练习的扩展，尝试解决链接以传递方式解释，即如果存在从节点A到B的链接序列，则A链接到B.必须为Mset中的所有这些节点分配一个与上述默认值不同的值。
要查找节点x的值，请扫描节点列表，找到不是x或最大节点M的最高值节点。棘手的部分是做有效率。解决方案并不难找到，这是你的一部分。 （提示：如果你的节点按值排序怎么办？）
希望能让你走上正确的道路。
work for the same reason. So fix that first and you will at least be able to run your code.
Next you will have to improve your algorithm. At the moment you are trying to solve the problem in a brute force way. That won't work within the given time limit -- and that's what the whole exercise is about. So start looking for a smarter way to approach things.
The first thing that comes to mind is that there is exactly one node with maximum value M. All nodes not linked to M will be assigned M's index. That's why index 5 appears three times in your example. So determining the maximum node and assigning it's index to all but that node itself is a reasonable default initialization.
Next find all the set of nodes that are linked to the maximum node M and let's call it Mset. (Your examples tells me that you interpret the term "linked" as non-transitive, i.e. A is linked to B only if there is an explicit link entry between them. As an extension to that exercise try to solve it for the case where "linked" is interpreted in a transitive manner, i.e. A is linked to B if there is a sequence of links that leads from node A to B). All these nodes in Mset must be assigned a value that is different from the above default.
To find that value for node x you scan the node list and find the highest value node that is not x or the maximum node M. The tricky part is to do that efficiently. The solution is not that hard to find and that is your part. (Tip: What if your nodes would be sorted by value?)
Hope that gets you on the right path.
这篇关于我该如何解决以下问题？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
