2.3.5.
. ,
B=, , i-
. i=1
, i=2 .
j-
i=n-j+1 i- .
i=a/n, 0 < a < 1, ,
a=1/2.
, B
, i- .
B ,
.
i- . ,
findi
/* */
int findi(int *s, int n, int i)
{
int c,j,k;
for (k=0; k<=i; k++)
for (j=k+1; j<=n; j++)
if (s[k] < s[j])
{ c=s[k];
s[k]=s[j];
s[j]=c;
}
return s[i];
}
i, s,
(n*i) . , findi
i,
.
i - B
. B K1 B'
B", , Ki -B', Ki>K1, Ki - B", Ki i
B'; j < i (i-j)
B".
,
,
.
i- B,
.
1. N<21, i- B
.
2. N>21 P=N/7 7 ,
mod(N,7) .
3. W (
) W M ( )
.. (P/2+1)- .
4. M B B' j
M, B" c N-j M. j>i
, B'. j=i
, M . j < i (i-j)-
B".
/* */
int search (int *b, int n, int i)
{
int findi(int *, int, int);
int t, m, j, p, s, *w;
if (n<21) return findi(b, n, i); /* 1 */
p=(int)(n/7);
w=calloc(p+1,sizeof(int)); /* 2 3 */
for (t=0; t < p; t++)
w[t]=findi(b+7*t, 7, 3);
if (n%7!=0)
{ w[p]=findi(b+7*p,n%7,(n%7)/2);
p++;
}
m=search(w, p, p/2);
free (w);
for (j=0, t=0; t < n; t++) /* 4 */
if (b[t]>=m) j++;
if (j>i)
{
for (p=0, t=0; p < n; t++)
if (b[t]>=m)
{ b[p]=b[t]; p++; }
m=search(b, j, i); /* B" */
}
if (j < i)
{
for (p=0, t=0; t < n; t++)
if (b[t] < m) b[p++]=b[t];
m=search(b, n-j, i-j); /* B" */
}
return m;
}
search i-
.
#include
#include
main()
{
int search (int *b, int n, int i);
int *b;
int l, i, k, t;
scanf("%d%d",&l,&i);
printf
("\n %d %d ",i,l);
b=(int *)(calloc(100,sizeof(int)));
for (k=0; k<100; k++)
b[k]=k; /* */
for (k=1; k < l/4; k++)
{ t=b[k]; /* */
b[k]=b[l-k]; /* */
b[l-k]=t;
}
k=search(b,l,i); /* */
printf ("\n %d\n\n",k);
return 0;
}
, ,
search 28*N
.
, N<21, findi
N*(N-1)/2, .. 28*N. , T
|
|
