报表难题
问题描述：给出n个数，求相邻两个数绝对值之差的最小值。有两种操作，一种是Q(表示你需要回答目前这些数的相邻两个数绝对值之差的最小值),一种是k（表示删原第K个数）。
文件输入：n，m（n,m<=100000）
n个数
以下每行一个共m个操作
文件输出：对应Q的回答
样例输入：
5 3
1 2 5 8 14
Q
K 2
K 3
Q
样例输出：
1
6
解法1：
#include <iostream>
using namespace std;
int totN, totM, nMin=0x7fffffff;
int iData[100010], iValue[100010];
void ReadData(void) {
scanf("%d%d",&totN,&totM);
int i;
for (i=1;i<=totN;i++) scanf("%d",&iData[i]);
for (i=1;i<totN;i++) {
iValue[i] = abs(iData[i+1] - iData[i]);
if (iValue[i] < nMin) nMin = iValue[i];
}
return;
}
void FindMin(void) {
int i, k(0x7fffffff);
for (i=1;i<totN;i++)
if (iValue[i]!=-1)
if (iValue[i] < k)
k = iValue[i];
nMin = k;
return;
}
void DeleteNum(int pos) {
int i, j, k, q;
k = iValue[pos];
iValue[pos] = -1;
i = pos-1; while (iValue[i]==-1 && i>0) i--;
q = iValue[i];
j = pos+1; while (iValue[j]==-1 && j<=totN) j++;
if (i!=0 && j<=totN) iValue[i] = abs(iData[j] - iData[i]);
if (j>totN) iValue[i] = 0x7fffffff;
if (k==nMin || q==nMin || iValue[i]<=nMin) FindMin();
return;
}
void Proc() {
char c; int i, j;
ReadData();
for (j=1;j<=totM;j++) {
do
scanf("%c",&c);
while (c!='Q'&&c!='k'&&c!='K'&&c!='q');
if (c=='Q' || c== 'q')
printf("%d\n",nMin);
else {
scanf("%d",&i);
DeleteNum(i);
}
}
return ;
}
int main() {
Proc();
return 0;
}
解法2：
#include<iostream>
using namespace std;
int Hash[10000000],pre[100001],next[100001],a[100001];
int main()
{
int N,M,i,k;
char ch;
cin>>N>>M;
a[0]=0;
for(i=1;i<=N;i++)
{
scanf("%d",a+i);
pre[i]=i-1;
next[i]=i+1;
Hash[abs(a[i]-a[i-1])]++;
}
Hash[a[1]]--;
int Min=0,temp;
for(i=1;i<=M;i++)
{ do
{
scanf("%c",&ch);
}while(ch==' '||ch=='\n');
if(ch=='Q')
{
while(Hash[Min]==0)Min++;
printf("%d\n",Min);
}
else
{
scanf("%d",&k);
if(pre[k]!=0)
Hash[abs(a[k]-a[pre[k]])]--;
if(next[k]!=N+1)
Hash[abs(a[k]-a[next[k]])]--;
next[pre[k]]=next[k];
pre[next[k]]=pre[k];
if(pre[k]!=0&&next[k]!=0)
{
temp=abs(a[pre[k]]-a[next[k]]);
if(temp<Min)Min=temp;
Hash[temp]++;
}
}
}
}
解法3：
#include<iostream>
using namespace std;
struct data{int v,l,r;}heap[100005];
struct node{int pre,next,v;}a[100005];
int num=0,n;
bool Delete[100005]={0};
void heapup()
{
int i=num;
while( i>1&&heap[i].v<heap[i/2].v){swap(heap[i],heap[i/2]);i/=2;}
}
void heapdown(int st)
{
int i=st,j;
while( i*2<=num)
{
j=i*2;
if( heap[j].v>heap[j+1].v&&j<num)j++;
if( heap[i].v>heap[j].v){ swap(heap[i],heap[j]);}
else break;
j=i;
}
}
int main()
{
int i,next,pre,x,m,p;
char c;
cin>>n>>m;
for( i=1;i<=n;i++)scanf("%d",&a[i].v);
a[1].pre=0;a[1].next=2;
heap[++num].v=abs(a[1].v-a[2].v);
heap[num].l=1;heap[num].r=2;
heapup();
for( i=2;i<n;i++)
{
a[i].pre=i-1;
a[i].next=i+1;
heap[++num].v=abs(a[i].v-a[i+1].v);
heap[num].l=i;heap[num].r=i+1;
heapup();
}
a[n].pre=n-1;a[n].next=0;
while( m--)
{
cin>>c;
if(c=='Q')
{
while( Delete[heap[1].l]||Delete[heap[1].r])
{
swap(heap[1],heap[num]);
num--;
heapdown(1);
}
printf("%d\n",heap[1].v);
}
else
{
scanf("%d",&x);
pre=a[x].pre;
next=a[x].next;
a[pre].next=next;
a[next].pre=pre;
if( pre!=0&&next!=0)
{
heap[++num].v=abs(a[pre].v-a[next].v);
heap[num].l=pre;
heap[num].r=next;
heapup();
}
Delete[x]=1;
}
}
return 0;
}