題目1:：
http://poj.org/problem?id=2833大意:：n個數,去掉最大的n1個和最小的n2個數,(n1+n2 < n)，求剩下的平均值。
題解：節省內存開銷，使用兩個堆維護，用最小堆維護最大的n1個數，用最大堆維護最小的n2個數，插滿時，只需比較兩個堆的front，再決定是否插入
代碼：
#include <stdio.h>
#include <string.h>
const int INF = 0x7fffffff;
template<typename _Type>
class MaxHeap
{
private:
_Type data[20];
int size;
int cur;
public:
MaxHeap(int _n):size(_n),cur(0)
{
memset(data,0,sizeof(data));
data[0] = INF;
}
~MaxHeap()
{
}
void clear()
{
memset(data,0,sizeof(data));
cur = 0;
data[0] = INF;
}
void push(_Type _value)
{
if(isFull())
{
return ;
}
cur ++;
int i;
for(i = cur; data[i/2] < _value;i/=2)
{
data[i] = data[i/2];
}
data[i] = _value;
}
void pop()
{
if(isEmpty())
return ;
int lastElement = data[cur];
data[cur] = 0;
--cur;
int child = 0;
int i = 0;
for(i = 1; i*2 <= cur; i = child)
{
child = i*2;
if(child != cur && data[child+1] > data[child])
{
++child;
}
if(lastElement < data[child])
data[i] = data[child];
else
break;
}
data[i] = lastElement;
}
int front()const
{
return data[1];
}
bool isFull()const
{
return cur >= size;
}
bool isEmpty()
{
return cur == 0;
}
};
template <typename _Type>
class MinHeap
{
private:
_Type data[20];
int size;
int cur;
public:
MinHeap(int _n):size(_n),cur(0)
{
memset(data,0,sizeof(data));
data[0] = -INF;
}
~MinHeap()
{
}
void clear()
{
memset(data,0,sizeof(data));
data[0] = -INF;
size = N;
cur = 0;
}
void push(_Type _value)
{
if(isFull())
return;
int i ;
cur++;
for(i = cur; data[i/2] > _value; i/= 2)
{
data[i] = data[i/2];
}
data[i] = _value;
}
void pop()
{
if(isEmpty())
return ;
int child = 0;
int i = 0;
int lastElement = data[cur];
data[cur] = 0;
--cur;
for(i = 1; i*2 <= cur; i = child)
{
child = i*2;
if(child != cur && data[child+1] < data[child])
{
child = child+1;
}
if(lastElement > data[child])
data[i] = data[child];
else
break;
}
data[i] = lastElement;
}
bool isFull()const
{
return cur >= size;
}
bool isEmpty()const
{
return cur == 0;
}
int front()const
{
return data[1];
}
};
int n,n1,n2;
void Test()
{
MinHeap<int> minHeap(n1);
MaxHeap<int> maxHeap(n2);
double sum = 0;
int tmp;
for(int i = 0; i < n; ++i)
{
scanf("%d",&tmp);
if(minHeap.isFull())
{
if(minHeap.front() < tmp)
{
minHeap.pop();
minHeap.push(tmp);
}
}
else
{
minHeap.push(tmp);
}
if(maxHeap.isFull())
{
if(maxHeap.front() > tmp)
{
maxHeap.pop();
maxHeap.push(tmp);
}
}
else
{
maxHeap.push(tmp);
}
sum += tmp;
}
while(!maxHeap.isEmpty())
{
sum -= maxHeap.front();
maxHeap.pop();
}
while(!minHeap.isEmpty())
{
sum -= minHeap.front();
minHeap.pop();
}
printf("%.6lf\n",sum/(n-n1-n2));
}
int main()
{
while(scanf("%d %d %d",&n1,&n2,&n) != EOF)
{
if(n1 == 0 && n2 == 0 && n == 0)
break;
Test();
}
return 0;
}
題目2：
http://poj.org/problem?id=3125題意：打印機取當前打印任務，若不是最高的打印任務，插到隊尾，計算給定的任務在什么時候完成打印
題解：使用簡單隊列模擬，que[m] == 0表示完成了打印
代碼：
#include <stdio.h>
#include <algorithm>
using namespace std;
int que[200];
void Test()
{
int n,m;
scanf("%d %d",&n,&m);
for(int i = 0; i < n; ++i)
{
scanf("%d",&(que[i]));
}
int time = 0;
int s = 0;
while(que[m] > 0)
{
if(que[s] > 0)
{
int maxP = -1;
for(int i = 0; i < n; ++i)
{
if(maxP < que[i])
{
maxP = que[i];
}
}
if(que[s] >= maxP)
{
++time;
que[s] = 0;
}
}
s = (s+1)%n;
}
printf("%d\n",time);
}
int main()
{
//freopen("data.txt","r",stdin);
int testcase;
scanf("%d",&testcase);
for(int i = 0; i < testcase; ++i)
{
Test();
}
return 0;
}
題目3：
http://poj.org/problem?id=2318題意：一個矩形，被n條直線劃分，然后給定點(x,y)，判斷所在區域
題解：點與直線的關系，二分法
代碼：
#include <stdio.h>
#include <string.h>
const int N = 5005;
int n,m,x1,y1,x2,y2;
int U[N];
int L[N];
int cnts[N];
void BinarySlove(int _x,int _y)
{
int low = -1;
int high = n;
int mid = 0;
while(low + 1< high)
{
mid = low + (high - low)/ 2;
double d = (double)(y1-y2)*(_x - U[mid]) + (double)(y1-_y)*(U[mid]-L[mid]);
if(d > 0)
{
low = mid ;
}
else
{
high = mid ;
}
}
cnts[high]++;
}
void Test()
{
memset(cnts,0,sizeof(cnts));
for(int i = 0; i < n; ++i)
{
scanf("%d %d",&U[i],&L[i]);
}
int xT,yT;
for(int i = 0; i < m; ++i)
{
scanf("%d %d",&xT,&yT);
BinarySlove(xT,yT);
}
for(int i = 0; i <= n; ++i)
{
printf("%d: %d\n",i,cnts[i]);
}
printf("\n");
}
int main()
{
//freopen("data.txt","r",stdin);
while(scanf("%d ",&n) != EOF)
{
if(n == 0)
break;
scanf("%d %d %d %d %d",&m,&x1,&y1,&x2,&y2);
Test();
}
return 0;
}
題目4：
http://poj.org/problem?id=2106題意：布爾表達式求解
題解：使用遞歸下降法LL求解
語法如下：
exp ---> (alt '|' )*alt
alt ---> (unit '&')*unit
unit ---> '('exp')' | '!'unit | 'F'|'V'
代碼：
#include <stdio.h>
#include <string.h>
char context[256];
int cur;
int len;
bool exp(char* _context);
bool unit(char* _context)
{
if(_context[cur] == '!')
{
++cur;
return !unit(_context);
}
else if(_context[cur] == '(')
{
++cur;
bool ret = exp(_context);
++cur;
return ret;
}
else if(_context[cur] == 'F')
{
++cur;
return false;
}
else
{
++cur;
return true;
}
}
bool alt(char* _context)
{
bool ret = unit(_context);
while(cur < len && _context[cur] == '&')
{
++cur;
bool ret2 = unit(_context);
ret = ret && ret2;
}
return ret;
}
bool exp(char* _context)
{
bool ret = alt(_context);
while(cur < len && _context[cur] == '|')
{
++cur;
bool ret2 = alt(_context);
ret = ret || ret2;
}
return ret;
}
void Test()
{
len = strlen(context);
cur = 0;
bool ret = exp(context);
if(ret)
printf("V\n");
else
printf("F\n");
}
int main()
{
//freopen("data.txt","r",stdin);
char token;
int testcase = 0;
while(token = getchar(),token != EOF)
{
++testcase;
memset(context,0,sizeof(context));
int k = 0;
while(token != '\n' && token != EOF)
{
if(token !=' ')
{
context[k++] = token;
}
token = getchar();
}
if(strlen(context) > 0)
{
printf("Expression %d: ",testcase);
Test();
}
}
return 0;
}posted on 2011-03-31 00:15
bennycen 閱讀(1182)
評論(3) 編輯 收藏 引用 所屬分類:
算法題解