【c++百日刷题计划】 ———— DAY4，带你轻松学习算法

n ( n ≤ 100 ) n(nle 100) n(n≤100) 名同学参加歌唱比赛，并接受 m ( m ≤ 20 ) m(mle 20) m(m≤20) 名评委的评分，评分范围是 0 0 0 到 10 10 10 分。这名同学的得分就是这些评委给分中去掉一个最高分，去掉一个最低分，剩下 m − 2 m-2 m−2 个评分的平均数。请问得分最高的同学分数是多少？评分保留 2 2 2 位小数。

第一行两个整数 n , m n,m n,m。
接下来 n n n 行，每行各 m m m 个整数，表示得分。

输出分数最高的同学的分数，保留两位小数。

7 6
4 7 2 6 10 7
0 5 0 10 3 10
2 6 8 4 3 6
6 3 6 7 5 8
5 9 3 3 8 1
5 9 9 3 2 0
5 8 0 4 1 10

6.00

• 1）记录单个人的成绩，进行排序和求和。
• 2）减去最大值和最小值，计算平均分。
• 3）和最大成绩比较，得到答案。

#include
using namespace std;
int main()
{
    int n,m;
    double MAX=INT_MIN;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        double tmp[10001],sum=0;
        for(int j=1;j<=m;j++)
        {
            cin>>tmp[j];    
            sum+=tmp[j];
        }
        sort(tmp+1,tmp+m+1);
        sum=sum-tmp[1]-tmp[m];
        sum/=(m-2);
        if(sum>MAX) MAX=sum;
    }    
    printf("%.2f",MAX);
    return 0;   
}

一矩形阵列由数字 0 0 0 到 9 9 9 组成，数字 1 1 1 到 9 9 9 代表细胞，细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。

第一行两个整数代表矩阵大小 n n n 和 m m m。

接下来 n n n 行，每行一个长度为 m m m 的只含字符 0 到 9 的字符串，代表这个 n × m n times m n×m 的矩阵。

一行一个整数代表细胞个数。

4 10
0234500067
1034560500
2045600671
0000000089

4

对于 100 % 100% 100% 的数据，保证 1 ≤ n , m ≤ 100 1 le n,m le 100 1≤n,m≤100。

• 1）题目相当于求连通块的个数。
• 2）当遍历到非 0 元素时，进行深度优先搜索，将这个元素周围的非零元素全变成 0。连通块次数加一。
• 3）遍历到全是非 0 元素时，输出答案。

#include
using namespace std;
int n,m;
char a[105][105];

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

int ans=0;

void dfs(int x,int y)
{
	if(a[x][y]=='0')return;
	a[x][y]='0';
	for(int i=0;i<4;i++)
	{
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(nx<1||nx>n||ny<1||ny>m)
		{
			continue;
		}
		else
		{
			dfs(nx,ny);
		}
	}
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(a[i][j]!='0')
			{
				ans++;
				dfs(i,j);
			}
		}
	}
	cout< 
第三题 小A点菜 
题目背景 
uim 神犇拿到了 uoi 的 ra（镭牌）后，立刻拉着基友小 A 到了一家……餐馆，很低端的那种。
 
uim 指着墙上的价目表（太低级了没有菜单），说：“随便点”。
 
题目描述 
不过 uim 由于买了一些书，口袋里只剩 
    
     
      
       
        M
       
      
      
       M
      
     
    M 元 
    
     
      
       
        (
       
       
        M
       
       
        ≤
       
       
        10000
       
       
        )
       
      
      
       (M le 10000)
      
     
    (M≤10000)。
 
餐馆虽低端，但是菜品种类不少，有 
    
     
      
       
        N
       
      
      
       N
      
     
    N 种 
    
     
      
       
        (
       
       
        N
       
       
        ≤
       
       
        100
       
       
        )
       
      
      
       (N le 100)
      
     
    (N≤100)，第 
    
     
      
       
        i
       
      
      
       i
      
     
    i 种卖 
    
     
      
       
        
         a
        
        
         i
        
       
      
      
       a_i
      
     
    ai​ 元 
    
     
      
       
        (
       
       
        
         a
        
        
         i
        
       
       
        ≤
       
       
        1000
       
       
        )
       
      
      
       (a_i le 1000)
      
     
    (ai​≤1000)。由于是很低端的餐馆，所以每种菜只有一份。
 
小 A 奉行“不把钱吃光不罢休”，所以他点单一定刚好把 uim 身上所有钱花完。他想知道有多少种点菜方法。
 
由于小 A 肚子太饿，所以最多只能等待 
    
     
      
       
        1
       
      
      
       1
      
     
    1 秒。
 
输入格式 
第一行是两个数字，表示 
    
     
      
       
        N
       
      
      
       N
      
     
    N 和 
    
     
      
       
        M
       
      
      
       M
      
     
    M。
 
第二行起 
    
     
      
       
        N
       
      
      
       N
      
     
    N 个正数 
    
     
      
       
        
         a
        
        
         i
        
       
      
      
       a_i
      
     
    ai​（可以有相同的数字，每个数字均在 
    
     
      
       
        1000
       
      
      
       1000
      
     
    1000 以内）。
 
输出格式 
一个正整数，表示点菜方案数，保证答案的范围在 int 之内。
 
样例 #1 
样例输入 #1 
4 4
1 1 2 2
 
样例输出 #1 
3
 
解题思路 
 
 
1）简单的01背包问题。
 
 
参考代码 
#include
using namespace std;
int dp[10500];
int main()
{
	int N,M;
	cin>>N>>M;
	dp[0]=1;
	for(int i=1;i<=N;i++)
	{
		int a;
		cin>>a;
		for(int j=M;j>=a;j--)
		{
			dp[j]=dp[j]+dp[j-a];
		}
	}
	cout< 
第四题 好奇怪的游戏 
题目背景 
《爱与愁的故事第三弹·shopping》娱乐章。
 
调调口味来道水题。
 
题目描述 
爱与愁大神坐在公交车上无聊，于是玩起了手机。一款奇怪的游戏进入了爱与愁大神的眼帘：***（游戏名被打上了马赛克）。这个游戏类似象棋，但是只有黑白马各一匹，在点x1,y1和x2,y2上。它们得从点x1,y1和x2,y2走到1,1。这个游戏与普通象棋不同的地方是：马可以走“日”，也可以像象走“田”。现在爱与愁大神想知道两匹马到1,1的最少步数，你能帮他解决这个问题么？
 
输入格式 
第1行：两个整数x1，y1
 
第2行：两个整数x2，y2
 
输出格式 
第1行：黑马到1,1的步数
 
第2行：白马到1,1的步数
 
样例 #1 
样例输入 #1 
12 16
18 10
 
样例输出 #1 
8 
9
 
提示 
100%数据：x1,y1,x2,y2<=20
 
解题思路 
 
 
1）题目问的是最少步数，这里就能看出应该用广度优先搜索。
2）用结构体存储位置和步数，使用STL模板库中的。将起点入队。
3）循环取队头元素，队头位置能到达的点都依次入队并标记为以访问。
4）到达(1，1)退出循环，将标记访问的数组归零，广度优先搜索下一起点。
 
 
参考代码 
#include
using namespace std;

int x1,x2,yy1,yy2;
struct node{
	int x,y;
	int step;
}now,top;
int dx[12]={2,2,-2,-2,-1,-1,1,1,-2,-2,2,2};
int dy[12]={2,-2,2,-2,-2,2,-2,2,1,-1,1,-1};
int b[1000][1000];
queue Q;

void bfs(int x,int y,int step)
{
	now.x=x;
	now.y=y;
	now.step=step;
	Q.push(now);
	while(!Q.empty()){
		top=Q.front();
		Q.pop();
		for(int i=0;i<12;i++)
		{
			int nx=top.x+dx[i];
			int ny=top.y+dy[i];
			if(nx>=1&&ny>=1&&nx<=50&&ny<=50&&b[nx][ny]==0)
			{
				now.x=nx;
				now.y=ny;
				now.step=top.step+1;
				Q.push(now);
				b[nx][ny]=1;
				if(nx==1&&ny==1)
				{
					cout<
	cin>>x1>>yy1>>x2>>yy2;
	bfs(x1,yy1,0);
	memset(b,0,sizeof(b));
	while(!Q.empty())Q.pop();
	bfs(x2,yy2,0);
	return 0;
}