给定一个迷宫，指明起点和终点，找出从起点出发到终点的有效可行路径，就是迷宫问题(maze problem)

迷宫可以以二维数组来存储表示。0表示通路，1表示障碍。注意这里规定移动可以从上、下、左、右四方方向移动。坐标以行和列表示，均从0开始，给定起点（0,0）和终点（4,4），迷宫表示如下：

左图每个方块表示一个状态，浅蓝色的表示遍历了该状态。

广度优先搜索即是按层数一层一层来遍历，先将一层全部扩展，然后再进行下一层。

利用队列先进先出（FIFO）的性质恰好可以来完成这个任务

对应的队列的情况：

具体过程：

1 每次取出队列首元素（初始状态），进行拓展

2 然后把拓展所得到的可行状态都放到队列里面

3 将初始状态删除

4 循环执行以上三步直到找到目标状态或者队列为空。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <queue>
using namespace std;
int mp[10][10];
bool inq[10][10];//passed set true

struct node{
    int x,y;
    node(int x=0,int y=0):x(x),y(y) {}
};
queue<node> q;
node frm[10][10];
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
bool bfs(){
    q.push(node(1,1));
    inq[1][1]=true;
    frm[1][1]=node(0,0);
    while (!q.empty()){
        node now = q.front();
        q.pop();
        if (now.x==5 && now.y==5){
            return true;
        }
        for(int i=0;i<4;i++){
            int tx=now.x+dx[i],ty=now.y+dy[i];
            if (!inq[tx][ty] && mp[tx][ty]==0){
                inq[tx][ty]=true;
                q.push(node(tx,ty));
                frm[tx][ty]=now;
            }
        }
    }
    return false;
}
void printans(int x,int y){
    if (x==0 && y==0)   return;
    printans(frm[x][y].x,frm[x][y].y);
    printf("(%d, %d)\n",x-1,y-1);
}
int main(){
    for (int i=0;i<=6;i++){
        for (int j=0;j<=6;j++){
            mp[i][j]=-1;
        }
    }
    for (int i=1;i<=5;i++){
        for (int j=1;j<=5;j++){
            scanf("%d",&mp[i][j]);
        }
    }
    bfs();
    printans(5,5);
    return 0;
}

函数的参数是什么样的？
结构体
struct A指针或引用
链表 数组
线性表
链表——无顺序数组
为什么是零散的状态？
1.可以动态申请内存
链表不需要任何静态的申请
eg.1
1 2 3 4 6 8 10
1 2 3 6 8 10
删除第四位
for(int i=3;i<=n;i++){
    a[i]=a[i+1]
}
链表插入一次就好
数组得挪很多次
链表访问比数组麻烦
链表结构体

声明一个指针函数
Struct link{
    int data;
    link* next;（内置类型的一个东西）
}
link *l;
l=new link();
(*l).data=15(l->data=15);
l->next =NULL;
link *head=new link();
link *push_back(link *p,int x)
{
    link *q= new link();
    q->data = x;
    q->next = NULL;
    p->next = q;
    return p->next;

}
Link *tmp = head;

链表访问复杂度较高（频繁插入删除，不频繁查找）
for(int i=1;i<10;i++)
{
    tmp = push_back(tmp,i);
}
栈 stack（抽象数据结构）
只能在顶端进行插入和删除
先进后出
队列（抽象数据结构）
可以用数组，也可用链表
数据结构
1.数据形态
2.数据操作

Q&A：

什么是二分法呢？

其实一直以来，在我的印象当中就是高中时候求解二元一次方程组解的时候所使用的算法。

也是现代计算器进行计算的原理。（即一直>>1[除以2]直到答案符合精度）

现在，我将通过系统的学习来为大家讲述二分法的更深入的地方。

#include <stdio.h>
#include <stdlib.h>
#include <cstdio>

struct info{
    double val;
    int pos;
};
int amount(info a[],int n)
{
    int i,j;
    for(i=0;i<n;i++)
    {
        for(j=i+1;j<n;j++)
        {
           if(a[j].val>a[i].val)
           {
               double t;
               t = a[i].val;
               a[i].val=a[j].val;
               a[j].val=t;
               int tt;
               tt=a[i].pos;
               a[i].pos=a[j].pos;
               a[j].pos=tt;
           }
        }
    }
    return 0;
}
int main()
{

    int M,N;
    int i;
    while(1)
    {
        scanf("%d %d",&M,&N);
        if(M==-1&&N==-1)
            break;
        info price[N]={0};
        int F[N]={0},J[N]={0};
        for(i=0;i<N;i++)
        {
            scanf("%d %d",&J[i],&F[i]);
            price[i].val=(double)J[i]/F[i];
            price[i].pos=i;
        }
        amount(price,N);
        double output=0;
        for(i=0;i<N;i++)
        {
            if(M>=F[price[i].pos])
            {
                output+=price[i].val*F[price[i].pos];
                M-=F[price[i].pos];
            }
            else if(M>0&&M<F[price[i].pos])
            {
                output+=price[i].val*M;
                M=0;
                break;
            }
        }
        printf("%.3lf\n",output);
    }
    return 0;
}

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
const int MAXN = 1010;
struct node
{
    double j,f;
    double r;
}a[MAXN];
/*
int cmp(const void *a,const void *b)//从大到小排序 
{
    struct node *c=(node *)a;
    struct node *d=(node *)b;
    if(c->r > d->r) return -1;
    else return 1;
}    */
bool cmp(node a,node b)
{
    return a.r  >  b.r;
}    
int main()
{
    int N;
    double M;
    double ans;
    while(scanf("%lf%d",&M,&N))
    {
        if(M==-1&&N==-1) break;
        for(int i=0;i<N;i++)
        {
           scanf("%lf%lf",&a[i].j,&a[i].f);
           a[i].r=(double)a[i].j/a[i].f;
        }    
        //qsort(a,N,sizeof(a[0]),cmp);
        sort(a,a+N,cmp);
        ans=0;
        for(int i=0;i<N;i++)
        {
            if(M>=a[i].f)
            {
                ans+=a[i].j;
                M-=a[i].f;
            }    
            else 
            {
                ans+=(a[i].j/a[i].f)*M;
                break;
            }    
        }   
        printf("%.3lf\n",ans); 
    }    
    return 0;
}

key3：without sort:

#include<stdio.h>
#include<stdlib.h>

const int MAXN = 1010;
struct node
{
    double j,f;
    double r;
}a[MAXN];
int cmp(const void *a,const void *b)//从大到小排序 
{
    struct node *c=(node *)a;
    struct node *d=(node *)b;
    if(c->r > d->r) return -1;
    else return 1;
}    
int main()
{
    int N;
    double M;
    double ans;
    while(scanf("%lf%d",&M,&N))
    {
        if(M==-1&&N==-1) break;
        for(int i=0;i<N;i++)
        {
           scanf("%lf%lf",&a[i].j,&a[i].f);
           a[i].r=(double)a[i].j/a[i].f;
        }    
        qsort(a,N,sizeof(a[0]),cmp);
        ans=0;
        for(int i=0;i<N;i++)
        {
            if(M>=a[i].f)
            {
                ans+=a[i].j;
                M-=a[i].f;
            }    
            else 
            {
                ans+=(a[i].j/a[i].f)*M;
                break;
            }    
        }   
        printf("%.3lf\n",ans); 
    }    
    return 0;
}

输入一行数字，如果我们把这行数字中的‘5’都看成空格，那么就得到一行用空格分割的若干非负整数（可能有些整数以‘0’开头，这些头部的‘0’应该被忽略掉，除非这个整数就是由若干个‘0’组成的，这时这个整数就是0）。

你的任务是：对这些分割得到的整数，依从小到大的顺序排序输出。        

初玩can，接触第三天的一道水题

第一程序为最初所写，第二个为参考优化后，

#include"stdio.h"
main()
{
    char c;
    while((scanf("%c",&c))!=EOF)
    {
         char a[1300];
         long long int b[1300],sum=0;
         int state=0,temp,k=0,i,j,l;
        for(i=0;c!='\t'&&c!='\n'&&c!=' ';i++)
        {
            a[i]=c;
            scanf("%c",&c);
        }
        a[i]='\0';
        for(j=0;j<i;j++)
        {
            if(a[j]=='5')
            {
                  if(state==1)
                    b[k++]=sum;
                  state=0;
                  sum=0;
            }
            else if(a[j]=='0')
              {
                   state=1;
                sum=sum*10+a[j]-'0';
              }
            else
                {
                   sum=sum*10+a[j]-'0';
                   state=1;
                }
        }
        if(state==1)
            b[k++]=sum;
            k--;
        for(j=0;j<k;j++)
            for(l=0;l<k-j;l++)
        {
            if(b[l]>b[l+1])
            {
                temp=b[l];
                b[l]=b[l+1];
                b[l+1]=temp;
            }
        }
        for(i=0;i<=k-1;i++)
        {
            printf("%lld ",b[i]);
        }
        printf("%lld\n",b[i]);
    }
}

2.

       对于一个存在着标准输入输出的C++控制台程序，一般会在#include <iostream>的下一行发现一句话，using namespace std。

       这句话其实就表示了所有的标准库函数都在标准命名空间std中进行了定义。其作用就在于避免发生重命名的问题。

#include <iostream>
using namespace std;
 
namespace ZhangSan
{
    int a=10; //张三把10赋值给了变量a
}
namespace LiSi
{
    int a=5; //李四把10赋值给了变量a
}
 
void main()
{
    int a=1;
    cout<<"张三定义的a="<<ZhangSan::a<<endl;
    cout<<"李四定义的a="<<LiSi::a<<endl;
    cout<<"主函数定义的a="<<a<<endl;   
}

上例中的“ZhangSan::a”和“LiSi::a”分别表示了调用张三命名空间中的a变量和李四命名空间中的a变量。这样的好处显而易见，那就是虽然张三和李四这两个程序员都定义了一个变量a，但是并不会出现重名的危险。

　2. 关于using namespace *

#include <iostream>
using namespace std;
 
namespace ZhangSan
{
    int a=10; //张三把10赋值给了变量a
}
namespace LiSi
{
    int a=5; //李四把10赋值给了变量a
}
 
void main()
{
    int a=1;
    using namespace ZhangSan;
    using namespace LiSi;
    cout<<a<<endl;
}

#include <iostream>
using namespace std;
 
namespace ZhangSan
{
    int a=10; //张三把10赋值给了变量a
}
namespace LiSi
{
    int a=5; //李四把10赋值给了变量a
}
 
void main()
{
    using namespace ZhangSan;
    using namespace LiSi;
    cout<<a<<endl;
}

吃糖果问题

复杂方法：

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
main()
{
    int i,t,j,N,f[50]={0};
    scanf("%d",&t);
    for(i=0;i<t;i++)
    {
        scanf(" %d",&N);
        for(j=0;j<N;j++)
        {
            scanf(" %d",&f[j]);
        }
        int k;
        for(j=0;j<N;j++)
        {
            for(k=0;k<N;k++)
            {
                if(f[i]<f[i+1])
                {
                    int middle = f[i];
                    f[i]=f[i+1];
                    f[i+1]=middle;
                }
            }
        }
        int flag=f[0];
        for(k=0;k<N;k++)
        {
            flag=flag-f[k+1];
        }
        if(flag>=2)
            printf("No\n");
        else
            printf("Yes\n");
    }

}

简便算法：

# include<stdio.h>
int main()
{
    long T, N;
    double candy, max,sum;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d", &N);
        max = sum = 0;
        while(N--)
        {
            scanf("%lf", &candy);
            max = max > candy ? max : candy;
            sum += candy;
        }
    sum -= max;
    if(max <= sum + 1)
        printf("Yes\n");
    else
        printf("No\n");
 }
}

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int is_prime(int a)
{
    int j;
    for(j=2;j<=sqrt(a);j++)
    {
        if(a % j ==0)
        {
            return 1;
        }
    }
    return 0;
}

int main()
{

    int x,y;
    while(1)
    {
        int flag=0;
        scanf("%d%d",&x,&y);
        int i;
        if(x==0&&y==0)
            return 0;
        if(x>y)
        {
            int t=y;
            y=x;
            x=t;
        }

        for(i=x;i<=y;i++)
        {
            int s;
            s = i*i+i+41;
            if(is_prime(s))
            {
                flag++;
                break;
            }
        }
        if(flag == 0)
            printf("OK\n");
        else
            printf("Sorry\n");
        }
    return 0;
}

很简单的一道题，发出来纯粹是因为无聊。这个题一直不能Accept，本来以为是我写错了，最后老师查出来是hoj问题。。。