好久没更新博客了，为了表示我还没放弃博客，特水水的更新一下，贴两道算法题吧。
不对，其实是应该算是数据结构题，因为没用到什么算法，只用到了数据结构。
其一是3750，小孩报数问题。
题目描述：有N个小孩围成一圈，给他们从1开始依次编号，现指定从第W个开始报数，报到第S个时，该小孩出列，然后从下一个小孩开始报数，仍是报到S个出列，如此重复下去，直到所有的小孩都出列（总人数不足S个时将循环报数），求小孩出列的顺序。
输入：第一行输入小孩的人数N（N<=64）
接下来每行输入一个小孩的名字(人名不超过15个字符)
最后一行输入W,S (W < N)，用逗号","间隔输出：按人名输出小孩按顺序出列的顺序，每行输出一个人名
这道题因为只有一组测试用例，并且数据量不大，<64。用暴力法也不会出现超时，超内存等问题。我用的是循环链表，不过不是动态的，因为数据量小，所以一开始直接用数组开辟64个地址空间，然后再将每个元素起来，首尾也相连。POJ上成绩是116K，0MS，第四名。
/*
@struct date 链表节点类型，包含字符数组和指向下一个节点的指针
@j 记录报数
*/
#include <stdio.h>
#define N 64
typedef struct date{
char name[16];
struct date *next;
}date;
int main(){
date a[N],*p;
int n,w,s,i,j;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%s",a[i].name);
a[i].next=(i==n-1)?a:&a[i+1];//将数组中元素关联起来，最后一个元素指向第一个元素，形成一个环
}
scanf("%d,%d",&w,&s);
j=0;
p=w<2?&a[n-1]:&a[w-2];
while(p&&n>0){
j++;
if(j==s){//报到指定数字
printf("%s\n",p->next->name);//输出小孩姓名
j=0;
p->next=p->next->next;//小孩出列（将下一个节点交给前一个节点的指针）
n--;
}else p=p->next;//向后报数
}
return 0;
}
其一是3061。
Description：A sequence of N positive integers (10 < N < 100 000), each of them less than or equal 10000, and a positive integer S (S < 100 000 000) are given. Write a program to find the minimal length of the subsequence of consecutive elements of the sequence, the sum of which is greater than or equal to S.
题目描述：有元素个数不超过N=100 000的整数序列，其中每个整数都小于10 000，然后求序列中元素个数最少的的一个子段（子段的元素之和大于等于S），S小于100 000 000
输入：第一行输入测试的数据数目，每个测试用例包含两行，第一行是N S，第二行是N个元素序列。
输出：每行输出一个求得的最小子段元素数目
这道题和最大子段类似，可以用单向队列来做，每个元素都要进次队列，维护队列中元素之和大于等于S，记录最小的队列中元素个数。POJ成绩：536K，63MS。
/*
@num 测试用例个数
@n 每个用例元素个数
@min 最小的队列元素个数
@sum 队列中元素之和
@front 队首
@rear 队尾
*/
#include <stdio.h>
#define N 100000
void main(){
int a[N],num,n,s,i,min,sum,front,rear;
scanf("%d",&num);
while(num--){
scanf("%d%d",&n,&s);
sum=0;min=N;
front=rear=0;
for(i=0;i<n;i++){
scanf("%d",&a[i]);
if(sum+a[i]<0){
sum=a[i];
rear=i;
}else{
sum+=a[i];
}
front++;/*printf("%d %d %d\n",front,rear,sum);*/
if(sum>=s){
while(rear<front){
if(sum-a[rear]<s){
break;
}else{
sum-=a[rear];
if(sum==0)
break;
rear++;
}
}
min=min>front-rear?front-rear:min;/*printf("%d=%d-%d\n",front-rear,front,rear);*/
}
}
printf("%d\n",min==N?0:min);
}
}
POJ测试数据中不包含负数，我贴的代码可以对包含负数的序列处理，S也可以为负数。
最后给个包含负数的测试用例：
输入：
3
10 -15
-18 0 -1 -10 -99 -91 -94 -99 -90 –98
10 15
1 -10 1 14 1 7 4 9 2 8
10 0
-1 –3 –2 0 2 12 –43 –4 –7 3
输出：
1
2
1
刚刚还跟静夜燃香说她那那个插件只在侧边栏显示成功正文不显示回复内容来着…
