Let us iterate over all different a__j. Since we need to maximize, then iterate all integer x (such_x_ divisible by a__j) in range from 2_a__j_ to M, where M — doubled maximum value of the sequence. For each such x we need to find maximum a__i, such a__i < x. Limits for numbers allow to do this in time O(1) with an array. After that, update answer by value. Total time complexity is O(nlogn + MlogM)
题解也没有特别懂。。。感觉和筛法有点类似。
不过学到了一个o(1)时间得到小于x的最大数是多少的做法。
Sort the array and just maintain another array A of 10^6 elements whereindex i stores element just smaller than i
For example consider sorted array [2,4,7,11], then
A(0 indexed) will be [-1,-1,-1,2,2,4,4,4,7,7,7,7,11...]
-1 means no element is smaller than i.
见代码中的b数组。
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2016年03月31日 星期四 14时23分39秒
4File Name :code/cf/problem/484B.cpp
5************************************************ */ 6 7#include<cstdio> 8#include<cstring> 9#include<iostream>10#include<algorithm>11#include<vector>12#include<queue>13#include<set>14#include<map>15#include<string>16#include<cmath>17#include<cstdlib>18#include<ctime>19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedeflonglongLL;25#define pi pair < int ,int >
26#define MP make_pair
2728usingnamespacestd;29constdoubleeps=1E-8;30constintdx4[4]={1,0,0,-1};31constintdy4[4]={0,-1,1,0};32constintinf=0x3f3f3f3f;33constintN=1E6+7;34intb[2*N];35intn;36intmain()37{38#ifndef ONLINE_JUDGE
39freopen("code/in.txt","r",stdin);40#endif
41cin>>n;42ms(b,-1);//b[i]表示比小于等于a[i]的元素里最大的。
43for(inti=1;i<=n;i++)44{45intx;46cin>>x;47b[x]=x;48}49for(inti=1;i<2*N;i++)if(b[i]==-1)b[i]=b[i-1];50// for ( int i = 1 ; i <= 20 ; i++) cout<<b[i]<<" ";
51intans=0;52for(intj=1;j<N;j++)53if(b[j]==j)54for(inti=j-1;i<2*N;i+=j)55if(j<=b[i]&&ans<b[i]%j)ans=b[i]%j;5657cout<<ans<<endl;5859#ifndef ONLINE_JUDGE
60fclose(stdin);61#endif
62return0;63}
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Petya loves computer games. Finally a game that he’s been waiting for so long came out!
The main character of this game has n different skills, each of which is characterized by an integer a__i from 0 to 100. The higher the number_a__i_ is, the higher is the i-th skill of the character. The total rating of the character is calculated as the sum of the values of for all i from 1 to n. The expression ⌊ x⌋ denotes the result of rounding the number x down to the nearest integer.
题目链接 题意：给出n个时间的开始和截止时间，保证没有两个时间的开始或者截止时间相同，问有多少个时间被包含在其他事件中。即aj < ai and bi < bj.
思路：没有两个事件的时间相同很关键。 那么我们可以直接按照开始时间为关键字排序，然后结束时间取之前发生了的（可能还没发生完）时间的结束时间的最大值即可。
