2017ACM暑期多校联合训练 - Team 6 1003 HDU 6098 Inversion (模拟)
Problem Description
Give an array A, the index starts from 1.
Now we want to know Bi=maxi∤jAj , i≥2.
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 Ai.
Limits
T≤20
2≤n≤100000
1≤Ai≤1000000000
∑n≤700000
Output
For each test case output one line contains n-1 integers, separated by space, ith number is Bi+1.
Sample Input
2
4
1 2 3 4
4
1 4 2 3
Sample Output
3 4 3
2 4 4
题意:
有一个有n个元素的数组,数组的下标从1到n,现在要求的就是从下标2开始的,下标不是它倍数的数值中的最大值。
分析:
因为要找的数值要与下标联系在一起,我们循环的往后找的话时间肯定会超的。
定义一个结构体,一个保存下标,一个保存对应的值,将结构体里面的元素对应的值按照从大到小的顺序排列好之后,循环数组只要找到第一个结构体里的下标不是当前要找的下标的倍数,就把对应的值输出来即可。
代码:
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 1e5+10;
struct node
{
ll m;///保存值
int x;///保存下标
} a[maxn];
inline bool cmp(node a, node b)
{
return a.m > b.m;
}
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
int n;
ll maxn,mm;
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
scanf("%lld", &mm);
a[i].x = i;
a[i].m = mm;
}
maxn = 0;
sort(a + 1,a + n + 1, cmp);
for(int i = 2; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
if(a[j].x % i != 0)
{
if(i==2)
printf("%lld",a[j].m);
else
printf(" %lld",a[j].m);
break;
}
}
}
printf("\n");
}
return 0;
}
最新文章
- itertools模块
- POJ 2031 Building a Space Station
- 每天一个linux命令--退出<;符号
- 网络应用发布到linux上的web服务器上页面上显示麻将牌式字符的问题
- 第一个C#应用 【搜索软件】
- VS打包
- JavaScript 开发规范要求详解
- 使用APT减少MVP的冗余代码
- 详解new/delete(整合)
- 通过Excel文件快速创建页面和数据表
- Shiro安全框架入门笔记
- Win10 快捷命令收集
- Testlink自动执行用例小程序
- 利用python 下paramiko模块无密码登录
- ios的图片解压
- (接上一条)解决ssh隧道断开自动重连的问题
- Java字符串split分割星号*等特殊字符问题(转)
- 系列文章--Enterprise Library文章总结
- Asp.net mvc 限制路由参数类型
- nodejs基础学习
热门文章
- Objective - C 之协议
- json_decode遇到的编码问题
- phaser3 微信小游戏若干问题
- resp.getWriter().print的注意点
- Linux进入单用户模式(passwd root修改密码)
- Linux内核分析第三周——构造一个简单的Linux系统MenuOS
- Qt实现截屏并保存(转载)
- 很好的c++和Python混合编程文章
- Educational Codeforces Round 20 C 数学/贪心/构造
- 洛谷P1948 [USACO08JAN]电话线Telephone Lines