Question

ACM问题 我的代码怎么老超时？？ http://acm.swjtu.edu.cn/JudgeOnline/showproblem?problem_id=1628

Give you a number sequence, can you tell me between the i-th number and the j-th number,which is the maximum and which is the minimum?

Input

The first line of the input is N and Q. N(N< 2^17) is the number of integers and Q(Q < 2^17) is the number of querys. The second line is the N integers and the following Q lines include two integers i and j(i <= j);

Output

For each query, output the maximum number and the minimum number.

Sample Input

10 5
8 2 839 -1 4 0 12 8 23 19
1 6
2 7
3 8
4 9
5 10

Sample Output

839 -1
839 -1
839 -1
23 -1
23 0
我的代码：
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<functional>
#include<vector>
#include<cmath>
using namespace std;
int a[132000];
int main()
{
int i,n,q,ii,jj,count=1;//cout<<pow(2,17)<<endl;
while(scanf("%d%d",&n,&q)!=EOF)
{
for(i=0;i<n;i++)
scanf("%d",&a[i]);
vector<int>ivector(a,a+n);
while(q--)
{
scanf("%d%d",&ii,&jj);
cout<<*max_element(ivector.begin()+ii-1,ivector.begin()+jj-1)<<" ";
cout<<*min_element(ivector.begin()+ii-1,ivector.begin()+jj-1)<<endl;
// printf("%d %d\n",max,min);
}
}
return 0;
}
第二个超时啊

Answer 1

你的算法需要优化。因为只有数组是固定的，只有一个，可以先建立一颗索引树，利用索引优化查询速度。
#include <iostream>
#include <vector>
#include <map>
using namespace std;

class IndexedArray
{
public:
IndexedArray(int n)
{
ValArr& arr(m_index[0]);
arr.resize(n);

for(int i = 0; i < n; i++) {
cin >> arr[i].max;
arr[i].min = arr[i].max;
}

buildIndex();
}

void query(int i, int j, int &maxNum, int &minNum) const;

private:
void buildIndex();

struct Values
{
int min, max, r1, r2;
};

typedef vector<Values> ValArr;
ValArr m_index[17];
int m_layer;
};

void IndexedArray::buildIndex()
{
for (m_layer = 0; m_index[m_layer].size() > 1; m_layer++) {
m_index[m_layer+1].resize(m_index[m_layer].size() / 2);
for (int j = 0; j < m_index[m_layer].size() / 2; j++) {
m_index[m_layer+1][j].max = max(m_index[m_layer][j*2].max, m_index[m_layer][j*2+1].max);
m_index[m_layer+1][j].min = min(m_index[m_layer][j*2].min, m_index[m_layer][j*2+1].min);
}
}
}

void IndexedArray::query(int i, int j, int &maxNum, int &minNum) const
{
int x = m_layer;
while ((1 << x) > j-i+1)
x >>= 1;
int k = (i >> x << x) + (1 << x);
if (k == j+1) {
maxNum = m_index[x][i >> x].max;
minNum = m_index[x][i >> x].min;
return;
}
int max1, max2, min1, min2;
query(i, k - 1, max1, min1);
query(k, j, max2, min2);
maxNum = max(max1, max2);
minNum = min(min1, min2);
}

void main()
{
int n, q;
cin >> n >> q;

IndexedArray a(n);
while(q--) {
int i, j, maxNum, minNum;
cin >> i >> j;
a.query(i-1, j-1, maxNum, minNum);
cout << maxNum << ' ' << minNum << endl;
}
}

Answer 2

区间最值RMQ
ST算法或者线段树
提供一个ST代码
/*
Range Minimum Query
Sparse Table (ST) algorithm
*/
#include<cstdio>
#include<cmath>
#define min(x,y) (x)<(y)?(x):(y)
//#define max(x,y) (x)>(y)?(x):(y)
#define N 100005
int n,s[N],dp[N][25],MAX[N][25],MIN[N][25];
void slove()//psotion
{
int i,j;
for(i=0;i<n;i++)
dp[i][0]=i;
for(j=1;1<<j<=n;j++)
for(i=0;i+(1<<j)-1<n;i++)
if(s[dp[i][j-1]]>s[dp[i+(1<<(j-1))][j-1]])
dp[i][j]=dp[i][j-1];
else
dp[i][j]=dp[i+(1<<(j-1))][j-1];
}
int find(int i,int j)
{
int k=int(log(j-i+1)/log(2));
if(s[dp[i][k]]>=s[dp[j-(1<<k)+1][k]])
return dp[i][k];
return dp[j-(1<<k)+1][k];
}
void ST()//value
{
int i,j;
for(i=0;i<n;i++)
MIN[i][0]=MAX[i][0]=s[i];
for(j=1;1<<j<=n;j++)
for(i=0;i+(1<<j)-1<n;i++)
{
MIN[i][j]=min(MIN[i][j-1],MIN[i+(1<<(j-1))][j-1]);
MAX[i][j]=max(MAX[i][j-1],MAX[i+(1<<(j-1))][j-1]);
}
}
int RMQ(int i,int j)
{
int a,b,k=int(log(j-i+1.)/log(2.));
a=max(MAX[i][k],MAX[j-(1<<k)+1][k]);//max
b=min(MIN[i][k],MIN[j-(1<<k)+1][k]);//min
return a;
}
int main()
{
int q,i,a,b;
while(scanf("%d",&n),n)
{
for(i=1;i<=n;i++)
printf("%d ",i);puts("");
for(i=0;i<n;i++)
{
scanf("%d",s+i);
}
slove();
ST();
scanf("%d",&q);
while(q--)
{
scanf("%d%d",&a,&b);
printf("pos:%d max:%d\n",find(a-1,b-1)+1,s[find(a-1,b-1)]);
printf("max:%d\n",RMQ(a-1,b-1));
}
}
}

Answer 3

我的代码：可以自己打照测试一些数据.
#include <iostream>
#include <map>
#include <cstring>
using namespace std;
int n;
char name[25];
string s[100002];
int c;
int counter=0;
map<string, int>m;
int result[100002];
void init()
{
for (int i=1; i<=n; i++)
{
scanf("%s",name);
int l=strlen(name);
sort(name, name+l);
s[i] = name;
}
}
void solve()
{
printf("Task #%d:\n", ++counter);
memset(result, 0, sizeof(result));
int num=0;
int f=1;
for (int i=1; i<=n; i++)
{
if(m[ s[i] ]!=0)
{
result[ m[ s[i] ] ]++;
}
else
{
m[ s[i] ]=f++;
result[f-1]++;
}
}
sort(result+1, result+f);
for (int i=1; i<f; i++)
{
if(result[i]==1)
{
printf("-->Group #%d has %d bunny.\n", i, result[i]);
}
else
{
printf("-->Group #%d has %d bunnies.\n", i, result[i]);
}
}
m.clear();
}
int main()
{
while(cin>>n)
{
init();
solve();
}
return 0;
}