泉水
Time Limit: 1000 MS Memory Limit: 65536 K
Total Submit: 2772(662 users) Total Accepted: 1074(597 users) Rating: Special Judge: No
Description
   Leyni是一个地址调查员,有一天在他调查的地方突然出现个泉眼。由于当地的地势不均匀,有高有低,他觉得如果这个泉眼不断的向外溶出水来,这意味着这里在不久的将来将会一个小湖。水往低处流,凡是比泉眼地势低或者等于的地方都会被水淹没,地势高的地方水不会越过。而且又因为泉水比较弱,当所有地势低的地方被淹没后,水位将不会上涨,一直定在跟泉眼一样的水位上。
由于Leyni已经调查过当地很久了,所以他手中有这里地势的详细数据。所有的地图都是一个矩形,并按照坐标系分成了一个个小方格,Leyni知道每个方格的具体高度。我们假定当水留到地图边界时,不会留出地图外,现在他想通过这些数据分析出,将来这里将会出现一个多大面积的湖。
Input
有若干组数据,每组数据的第一行有四个整数n,m,p1,p2(0<n,m,p1,p2<=1000),n和m表示当前地图的长和宽,p1和p2表示当前地图的泉眼位置,即第p1行第p2列,随后的n行中,每行有m个数据。表示这每一个对应坐标的高度。
Output
输出对应地图中会有多少个格子被水充满。
Sample Input
3 5 2 3
3 4 1 5 1
2 3 3 4 7
4 1 4 1 1
Sample Output
6

题目链接:HRBUST OJ 1143 泉水

AC代码:

#include <stdio.h>
#include<iostream>
#include<string.h>
using namespace std;

int a[1010][1010];
bool b[1010][1010];
int sum = 0;

void search(int p1,int p2,int h,int n ,int m){
    b[p1][p2] = false;
    if(a[p1][p2]<=h){
        sum++;
    }
    if(p1+1<n && b[p1+1][p2] && a[p1+1][p2]<=h){
        search(p1+1,p2,h,n,m);
    }
    if(p1-1>=0 && b[p1-1][p2] && a[p1-1][p2]<=h){
        search(p1-1,p2,h,n,m);
    }
    if(p2-1>=0 && b[p1][p2-1] && a[p1][p2-1]<=h){
        search(p1,p2-1,h,n,m);
    }
    if(p2+1<m && b[p1][p2+1] && a[p1][p2+1]<=h){
        search(p1,p2+1,h,n,m);
    }

}



int main()
{
     int n,m,p1,p2;
    while(cin>>n>>m>>p1>>p2){
         memset(b,true,sizeof(b));

        sum = 0;
        --p1;
        --p2;
        for(int i = 0;i<n;i++){
            for(int j = 0;j<m;j++){
                cin>>a[i][j];
            }
        }
        int h = a[p1][p2];
        sum = 0;
        search(p1,p2,h,n,m);
        cout<<sum<<endl;
    }
}

 

如何获取所有全排列情况?STL中的代码非常精妙,利用next_permutation的返回值,判断是否全排列结束(否则将死循环)。对于给定的一个数组,打印其所有全排列只需如下:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

void all_permutation(int arr[], int n)//获得C++的全排列
{
    sort(arr,arr+n);    // sort arr[] in ascending order
    do{
        for(int i=0; i<n; printf("%d ",arr[i++]));
        printf("\n");
    }while(next_permutation(arr,arr+n));
}

int main(){
     int a[5]={1,2,3};
      all_permutation(a,3);
}

 

#include <iostream>
#include <string>
using namespace std;


void merge(int a[],int c[],int first,int mid,int last){
    int i = first;
    int j = mid+1;
    int k = first;
    while(i<=mid && j<=last){
        if(a[i] <= a[j]){
            c[k] = a[i];
            k++;
            i++;
        }
        else{
            c[k] = a[j];
            k++;
            j++;
        }
    }
    while(i<=mid){
        c[k]=a[i];
        k++;
        i++;
    }
    while(j<=last){
        c[k]=a[j];
        k++;
        j++;
    }
for(int i=first;i<=last;i++)a[i]=c[i];
}

void mergeSort(int a[],int c[],int first , int last){
    if(first<last){
    int mid = (first+last)/2;
    mergeSort(a,c,first,mid);
    mergeSort(a,c,mid+1,last);
    merge(a,c,first,mid,last);
}
}

int  main(){
    int a[99] = {5,4,3,2,1};
    int c[99];
    mergeSort(a,c,0,4);
    for(int i = 0 ;i<5;i++){
        cout<<a[i]<<" ";
    }
}

归并排序的思想是分而治之,将数组不断分割,最后将两部分数组合并,通过判断第一部分和第二部分数组当前元素的大小来合并,不断合并直到完成排序。

归并排序是稳定的排序方式,归并排序的比较次数小于快速排序的比较次数,移动次数一般多于快速排序的移动次数,归并排序的时间复杂度为O(nlogn),空间复杂度为O(n)。

有时候scanf(“%c”,&ch)本应该阻塞等待用户输入一个char型数据的,但为什么会跳过呢?
例:在该程序段中,
int year;
    printf("请输入一个年份:\n");
    scanf("%d",&year);
   // setbuf(stdin,NULL);//或者直接用getchar();
    //在键盘输入一字符,显示其类型(数字、大写字母、小写字母、其他)
    char ch;
    printf("请输入一个字符:\n");
    scanf("%c",&ch);
    if(ch>='1'&&ch<='9')
        printf("this is digital\n");
    else if (ch>='A'&&ch<='B')
        printf("this is capital letter\n");
    else if (ch>='a'&&ch<='z')
        printf("this is letter\n");
    else
        printf("other!\n”);

 

会输出:
请输入一个年份:
2000
请输入一个字符:
other!
 
例2:
以下程序段:
while (n<=0)
{
printf(“请输入字符串长度:\n”);
scanf(“%d”,&n);
}
setbuf(stdin,NULL); //<1>
char a[n],b[n];
printf(“输入字符串:\n”);
for (int i=0; i<n; i++)
{
scanf(“%c”,&a[i]);
}
printf(“输出字符串为:\n”);
for (int i=0; i<n; i++)
{
b[i]=a[n-1-i];
printf(“%c”,b[i]);
}
如果将<1>语句去除,会使结果错误
例:
请输入字符串长度:
5
输入字符串:
hello
输出字符串为:
lleh

纠其根源,我们先来了解一下scanf()是怎么接受数据的。

首先,当我们的pc指向scanf这句时,系统并不是等待用户输入,而是判断输入缓冲区有没有符合格式的内容,如果有,则直接读取。

知道了这个,我就应该明白,scanf(“%c”,&ch);不是没有读到数据,而是读到了我们不知道的数据。

那问题又来了,它读到了什么??

好吧,这就要说到行缓存;

我们用scanf()的时候都要按下enter键,那enter键按了之后去哪儿了??

好吧,问题基本应该知道了,enter键也进入了输入缓存区,也就是scanf(“%c”,&ch);

读到了’\n’;

解决办法,很简单,既然缓存区有东西,那我们就清空它呗~~

setbuf(stdin,NULL);//这个windows和linux下都可以
fflush(stdin);//这个只能windows;

 

 

有没有想过,当我们定义一个对象的时候,该对象是定义在堆上还是栈上的呢?

现在,假设你已经清楚什么是堆,什么是栈。

如果需要在堆上创建对象,要么使用C++的new运算符,要么使用C语言的malloc系列函数。这点没有异议。

那么假如有一个类A,语句如下:

A a;

此时,a是在栈上分配的吗?

其实,这行语句的含义是,使对象a具有“自动存储(automatic storage)”的性质。所谓“自动存储”,意思是这个对象的存储位置取决于其声明所在的上下文。

如果这个语句出现在函数内部,那么它就在栈上创建对象。

如果这个语句不是在函数内部,而是作为一个类的成员变量,则取决于这个类的对象是如何分配的。

一般来说,如果你用new来生成的对象都是放在堆中的,而直接定义的局部变量都是放在栈中的,全局和静态的对象是放在数据段的静态存储区中。

那么,该如何定义一个只能在堆/栈上生成对象的类呢?

只能在堆上

方法:将析构函数设置为私有

原因:C++ 是静态绑定语言,编译器管理栈上对象的生命周期,编译器在为类对象分配栈空间时,会先检查类的析构函数的访问性。若析构函数不可访问,则不能在栈上创建对象。

如下所示:

#include <iostream>
using namespace std;

class A{
  public:
    A(){};
  private:
    ~A(){};//将析构函数设为私有
};

int main(){
    A a;//无法通过编译,提示A类的析构函数是私有的
    A *aa = new A();//通过编译,在堆上生成对象
}

 

只能在栈上

方法:将 new 和 delete 重载为私有

原因:在堆上生成对象,使用 new 关键词操作,其过程分为两阶段:第一阶段,使用 new 在堆上寻找可用内存,分配给对象;第二阶段,调用构造函数生成对象。将 new 操作设置为私有,那么第一阶段就无法完成,就不能够在堆上生成对象。

#include <iostream>
using namespace std;

class A{
  public:
    A(){};
    ~A(){};
   private:
    void * operator  new ( size_t  t){}//重载new运算符为私有类型
    void operator delete ( void * ptr){}//重载delete运算符为私有类型
};

int main(){
    A a;//通过编译,在栈上建立了对象
    A *aa = new A();//无法通过编译,提示new运算符是A的私有成员
}

 

翻阅以前的代码,时常会看到如下代码:

if(str.size() == 0) {}
if(!vec.size())     {}
if(!list.size())    {}
// ......

这些例子中只是把 size() 的返回值简单地进行布尔逻辑比较,意思是判断容器空与非空。

代码没有逻辑问题,只是可能效率不够高。

在C++的标准库容器中都有一个 empty() 方法,返回布尔值,表明容器当前是否为空。

使用 size() 判断容器非空与否的不好之处在于:某些标准库中的实现中对某些容器的 size() 求值操作不是线性的。

比如 std::list<>,在某些实现中,每一次调用 size() 都会遍历整个 list 来求 size,这会带来一定的性能问题。如果是线性容器则不会有此问题。

总之,如果只是想判断空与非空,则应总是使用 empty(),而不是 size()

#include <iostream>
#include<vector>
using namespace std;


void quickSort(vector<int>&a,int first , int last){
    if(first >= last){
        return;
    }
    int i = first,j = last;
    int key = a[first];//选择当前数字中第一个数作为基准key
    while(i < j){
        while(i < j && a[j] > key){
            j--;
        }
        a[i] = a[j];//在数组的后面遇到了比基准key小的数,放到前面去
        while(i < j && a[i] < key){
            i++;
        }
        a[j] = a[i];//在数组的前面遇到了比基准key大的数,放到后面去,刚好覆盖上次那个比基准大的数的位置
    }
    a[j] = key;//此时i==j,这个位置应该就是我们的基准key应该放到的地方
    quickSort(a,first,j-1);//递归对目前的key左边部分使用快速排序
    quickSort(a,i+1,last );//递归对目前的key右边部分使用快速排序
}

int main()
{
    vector<int>a = {22,32,54,79,154,2,10,0,-6,48,99};
    quickSort(a,0,10);
    for(int i = 0;i<11;i++){
        cout<<a[i]<<" ";
    }
}

快速排序是综合性能最好的排序方式,平均时间复杂度为O(nlogn),且不具有稳定性。

当序列已经是递增序列的时候,快速排序此时的时间复杂度最高,为O(n²)。