HDU 6098 17多校6 Inversion（思维+优化）

Problem Description

Give an array A, the index starts from 1.
Now we want to know

Input

The first line of the input gives the number of test cases T; T test cases follow.
Each case begins with one line with one integer n : the size of array A.
Next one line contains n integers, separated by space, ith number is

Output

For each test case output one line contains n-1 integers, separated by space, ith number is

Sample Input

1 2 3 4

1 4 2 3

Sample Output

3 4 3

2 4 4

题意：给出a序列，求b序列，bj=max(ai)(i%j!=0)

题解：对a排序后，直接查找TLE。因此将排序后的最大值，将b中可以取它的值先赋值赋好。然后剩余数再去查找，就会节省很多时间。应该有更好的方法？

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<queue>
 5 #include<map>
 6 #include<vector>
 7 #include<cmath>
 8 #include<cstring>
 9 
10 
11 using namespace std;
12 int t,n;
13 struct  node
14 {
15     long long k;
16     int pos;
17 }a[100005];
18 int b[100005];
19 bool cmp(node a,node b)
20 {
21     return a.k>b.k;
22 }
23 
24 int main()
25 {
26     scanf("%d",&t);
27     for(;t>0;t--)
28     {
29         scanf("%d",&n);
30         for(int i=1;i<=n;i++)
31         {
32             scanf("%lld",&a[i].k);
33             a[i].pos=i;
34         }
35         sort(a+1,a+1+n,cmp);
36         memset(b,-1,sizeof(b));
37         for(int j=2;j<=n;j++)
38         {
39             if(a[1].pos%j!=0)
40                 b[j]=a[1].k;
41         }
42         for(int i=2;i<=n;i++)
43         {
44             if(b[i]!=-1)
45                 continue;
46             for(int j=1;j<=n;j++)
47             if (a[j].pos%i!=0) 
48             {
49                 b[i]=a[j].k;
50                 break;
51             }
52         }
53         printf("%d",b[2]);
54         for(int j=3;j<=n;j++)
55             printf(" %d",b[j]);
56         printf("
");
57     }
58     return 0;
59 }

HDU 6098 17多校6 Inversion（思维+优化）

相关推荐