算法考核总结

算法考核总结

不久前进行了一次算法考核，让我见识到了自己的渺小，双指针不会用。

先放只飞鸟缓一下：

目录

1.

 思路：

一.判断最大和

二.起止位置

代码：

 2.

 思路：

今年暑假不AC：

代码如下：

 再说此题：

代码如下：

---

 

 

1.

 

 思路： 一.判断最大和

1.假设有1 2 3 4 5项。

     首先，1项+2项，其次，判断 2项+3项 与 1项+2项 的关系，若大于，则子序列向后推进1，若小于，则跳过本次循环。之后一直往后判断，若之后的所有项相加都大于前几项之和（若前几项的和为正数，则大于0是必要条件），则最大的子序列是所有的项数相加之和（和要大于前一项）

解释：若1+2项>0,1+2+3项<1+2项，但1+2+3+4项>1+2项，但1+2+3+4+5项<1+2+3+4项，且从第2，3，4项开始的所有序列之和均<1+2+3+4项，则最大子序列为1+2+3+4项。

这个判断只需要一个for循环。

二.起止位置

首先需要两个变量，分别用来存储开始，和结束的位置。

开始的位置是第一个，如果项数之和>0，则这个first的位置不变。

结束的位置随序列的增加而增加，若本次的循环跳过，则+2个位置

代码：

#include   

int main()  
{  
    int j,i,k,n,m,t;  
    int a[100002];  
    scanf("%d",&t);  
    for (j=1;j<=t;j++)  
    {  
        scanf("%d",&n);  
        for (i=0;id)  //判断多加一项后的值与加之前的关系
            {  
                d=s; //令d==和的值。
				f=m; //保存开始的位置
				l=i+1;  //保存结束的位置
            }  
            if (s<0)  
            {  
            s=0;  如果成立，只是和的值重新开始，但d，f，l已经事先存好了
			m=i+2;  //m的位置向后退两个
            }  
        }  
      
        printf("Case %d:n%d %d %dn",j,d,f,l);  
        if (j!=t)   //满足只有两个样例之间空格
        {  
            printf("n");  
        }  
    }  
    return 0;  
}

 2.

 

 思路：

在说这道题之前，有一个题与他类似。

如下：

今年暑假不AC：

 

 1. 先按照结束时间进行排序，若相同，再按照开始时间进行排序。

2.依次比较前一个的结束时间与下一个的开始时间之间的关系。

代码如下：

#include
struct zhuanbo   //结构体来定义，因为要实现同时交换
{
	int a;
	int b;
}zhuanbo[101];

int main()
{
	struct zhuanbo t;
	int n,c=1;
	while(scanf("%d",&n)!=EOF && n!=0)
	{
		for(int i=0;izhuanbo[j+1].b)//首先按照结束时间
				{
					t=zhuanbo[j];
					zhuanbo[j]=zhuanbo[j+1];
					zhuanbo[j+1]=t;
				}
				if(zhuanbo[j].b==zhuanbo[j+1].b)//其次按照开始时间
				{
					if(zhuanbo[j].a=t)//比较上一个的结束时间与下一个的开始时间
			{
				c+=1;
				t=zhuanbo[i].b;
			}
		}	
		printf("%dn",c);
		c=1;
	}
	return 0;
}

 再说此题：

1.首先比较保质期的长短。若保质期的时间相同，则比较利润数。

2.若保质期相同，则取利润最大的那一个，若保质期不相同，则直接取保质期短的那一个结构体里面的利润，（因为利润与保质期已经按顺序排好了）。如此进行比较。

代码如下：

#include

struct stu
{
	int a;
	int b;
}stu[10001];

int main()
{
	struct stu t;
	int n,c=0;
	while(scanf("%d",&n)!=EOF)//实现多组输入
	{
		int a; 
		for(int i=0;i=stu[j+1].a)
					{
						t=stu[j];
						stu[j]=stu[j+1];
						stu[j+1]=t;
					}
				}
			}
		}
		for(int i=n;i>=0;i--)
		{
			if(stu[i].b==stu[i+1].b) //当保质期相同时，取利润最大的那一个
			{
				continue;
			}else{
				c=c+stu[i].a;  //保质期不相同，直接取上一个保质期对应的利润
			}
		}
		printf("%dn",c);
		c=0;
	}
	return 0;
}

 这个题的思路就是这，但是如果直接使用冒泡排序进行运算的话，会超时，所以需要用快排，或者是直接调用排序函数（前提是保质期不相同）。

作为一个算法小白，我的分享就是这，如果有错误，欢迎指正。感谢观看！！！