近期不熟知识点学习总结

一.函数

参数传递
定义：参数传递是指用函数调用的实参来初始化函数形参存储区的过程。
1.函数的形参是局部对象，仅在函数的作用域内可见
2.每次调用函数时，会创建形参变量，并用传入的实参初始化形参
3.如果形参是引用类型，形参将绑定到对应的实参上，否则，将实参的值复制后赋给形参
4.参数传递方式
I.传值，按值传递参数。当实参的值被复制给形参时，形参和实参是两个独立的对象，实参被称为按值传递，或传值调用函数
II.传指针：使用指针参数是传地址值。

void pswap(int *pv1, int *pv2){ 
int t;
t = *pv1;  *pv1 = *pv2;  *pv2 = t; 	//间接访问
}
int main(){
int ival1 = 10, ival2 = 20;
int *p1 = &ival1;
int *p2 = &ival2;
cout << ival1 << " " << ival2 <<endl;
pswap(p1,p2);
cout << ival1 << " " << ival2 <<endl;
}

III.传引用，按引用传递参数。此时，引用形参绑定到实参，是实参对象的别名。
函数操纵的形参是实参的别名，因而可以改变实参的值.
传递引用参数，交换两个变量的值.

void swap(int& rv1, int& rv2){ 
int t;
t = rv1;
rv1 = rv2;
rv2 = t;
}
int main(){
int ival1 = 10;
int ival2 = 20;
cout << ival1 << " " << ival2 <<endl;
swap(ival1,ival2);
cout << ival1 << " " << ival2 <<endl;
}

使用引用参数传递大对象,使用const限定可以避免实参被修改

5.参数传递方式的选择

数组和函数作参数时必须传指针
拷贝构造函数的参数必须传引用

数组作参数时，将传递数组第一个元素的地址
将形参数组声明为const表明不希望改变数组元素

6 参数类型检查

void func(int* pi){...}
int a = 10;
const int b = 5;
func(&a);	//正确：形参int*类型，实参int*类型，类型匹配
func(&b);	//错误：实参const int*类型，不能转换为int*类型

void goo(const int* cp){...}
goo(&a);	//正确：实参int*类型可以转换为形参const int*类型
goo(&b);	//正确：实参const int*类型，匹配

7 函数声明
I. 函数在使用之前必须声明
II. 一个函数可以在程序中多次声明
III. 函数定义也可以被用作声明，但是函数在程序中只能定义一次

8 返回引用
将函数声明为返回引用，则不需要对return语句中的表达式进行复制，而是返回对象本身，函数返回的引用仅是它所指向对象的一个别名。

//找出s1和s2中比较短的一个并返回其引用
const string& shorter(const string& s1, const string& s2)
{	
return (s1.size() <= s2.size()) ? s1 : s2;
}
//函数返回结果时不会真正复制对象，返回的就是s1或s2本身

例：代码

#include <iostream>
#include <string>
using namespace std;
string& longerString(string &sa, string &sb){
	return sa.size() > sb.size() ? sa : sb;
					//返回对象本身，不进行复制
}
int main(){
    string s1 = "cat",s2 = "at";
    longerString(s1 , s2)[0] = 'h';	
					//相当于s1[0] = 'h';
    cout << s1 << endl;
}

#include <iostream>
using namespace std;
int& searchElement(int array[],int index){
	return array[index];
		//返回的不是array[index]的副本，而是array[index]本身
}
int main(){
    int arr[5] = {0,1,2,3,4};
    searchElement(arr , 2)=5;
    cout<<"arr[2]:"<<arr[2]<<endl;
}

9 局部static对象
I. 声明为static的局部对象是静态存储的
II. static对象在控制流程第一次到达其定义点时被初始化，如果没有提供初始值，就被自动初始化为0值
III. 在函数的后续调用中，初始化语句被跳过
IV. 静态对象的值在函数的多次调用之间保持有效，生存期会延续到整个程序结束，但它的作用域仍然是局部的,因此，需要在同一函数的两次调用之间保留某些数据时可以使用局部static对象
V. 比自动对象生存期长，比全局变量作用域小更安全

#include <iostream>
using namespace std;
void fun(){
static int sval = 5; 	//第一次调用函数时初始化
int ival = 5;
sval++;
ival++;
cout<<"sval="<<sval<<" ival="<<ival<<endl;
}
int main(){
for (int i =0 ; i < 3; i ++) fun();
}

Output

sval=6 ival=6
sval=7 ival=6
sval=8 ival=6

通过这段代码可以清楚地看到static的作用

二 贪心算法中一种类型的题（贪心）

接下来我将从几道题来总结一下这一种类型的题的共通之处

1.

题目大意：
小明有n项作业，完成一门作业需要一天，然后有两行数据，第一行是每项作业交的最晚时间，第二行是每一项作业如果完不成小明就要被扣的分数，问小明最少被扣多少分

Sample Input
3
3
3 3 3
10 5 1
3
1 3 1
6 2 3
7
1 4 6 4 2 4 3
3 2 1 7 6 5 4

Sample Output
0
3
5

思路：先按照扣分从大到小排序，分数相同则按照截止日期从小到大排序。。
然后按顺序，从截止日期开始往前找没有占用掉的时间。
如果找不到了，则加到罚分里面

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1010;
struct Node
{
    int d,s;
}node[MAXN];
bool used[10000];
bool cmp(Node a,Node b)//排序，对于此种题目所进行的排序
{
    if(a.s==b.s)
    {
        return a.d<b.d;
    }    
    return a.s>b.s;
}        
int main()
{
    int T;
    int n;
    int j;
    scanf("%d",&T);
    while(T--)//表示输入几组数据
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++) scanf("%d",&node[i].d);
        for(int i=0;i<n;i++) scanf("%d",&node[i].s);
        sort(node,node+n,cmp);
        memset(used,false,sizeof(used));//将数组清空
        int ans=0;
        for(int i=0;i<n;i++)
        {
            for(j=node[i].d;j>0;j--)
            {
                if(!used[j])
                {
                    used[j]=true;//这一天被占用，标记
                    break;//如果找到可用的天，则跳出第二个循环
                }    
            }    
            if(j==0)
              ans+=node[i].s;//表示没找到天
        }    
        printf("%d\n",ans);
    }    
    return 0;
}    

2.
题目大意：
超市里有n个产品要卖，每个产品都有一个截至时间dx（从开始卖时算起），只有在这个截至时间之前才能卖出并且获得率润dy。有多个产品，所有可以有不同的卖出顺序，每卖一个产品要占用1个单位的时间，问最多能卖出多少利润。

Sample Input
4 50 2 10 1 20 2 30 1
7 20 1 2 1 10 3 100 2 8 2
5 20 50 10

Sample Output
80
185

思路：
先把所有产品按照利润从大到小排序，然后这个把这个放在截止日期那天卖出，并做好标记，如果截至日期那天已经有其他产品占用了，那么可以把这个产品卖出的时间往前推，直到找到可以卖的那一天并标记好。
假设一个产品a占用了一个日期后，那么如果下次又有一个产品b和产品a的截止日期是相同的，但是那个日期以被占用了，所以就要往前移动1天，那么就可以用并查集进行标记，在a占用了那个日期后，把a的截止日期指向前一个日期，这样的话，可以直接查找到他要占用到哪一个时间。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=10005;
int visited[maxn]; //代表第i天是否有卖商品
 struct node{
    int p,d;
};
 bool cmp(node a,node b){
    return a.p>b.p;
}
 int main()
{
    int n;
    while(~scanf("%d",&n)){
        memset(visited,0,sizeof(visited));
        node a[maxn]; //存商品
        for(int i=0;i<n;i++){
            scanf("%d%d",&a[i].p,&a[i].d);
        }
        sort(a,a+n,cmp);
        int sum=0;
        for(int i=0;i<n;i++){
            for(int j=a[i].d;j>=1;j--){ //在截止日期之前卖出就行
                if(visited[j])
                    continue;
                visited[j]=1;
                sum+=a[i].p;
                break;
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}

总结：这两个题目的核心之处在于两个for循环，题目的本质都是一样，都是以某一种特定的方法排好序，然后执行两个for循环进行遍历，第一个循环将所有元素遍历一遍，第二个for循环从某一个当前位置开始向前遍历，直到找到符合的位置，然后用continue跳出第二个循环，或是找到第一个位置也不符合题意