第十二周

末蓝、 2022-10-15 04:53 202阅读 0赞

### 课后练习题 ###

*  A、XP的素数
 *   *  代码
 *  B、XP的点滴
 *   *  代码
 *  C、今年暑假不AC
 *   *  代码
 *  D、最优装载
 *   *  代码
 *  E、XP的小视频
 *   *  代码
 *  F、最小生成树（Prim）
 *   *  代码

# A、XP的素数 #

**题目描述**

*  XP最近对素数很痴迷，特别是那些特殊的素数，其中有一类素数被称为孪生素数。其定义如下：如果一个数k是素数，k+2也是素数，那么k和k+2成为一对孪生素数。请计算一个给定区间m和n（0<m<n）中孪生素数对的个数。

**输入**

*  单组输入数据 m n (0<m<n<1000)

**输出**

*  请输出一行结果:区间\[m,n\]中孪生素数对的个数

**样例输入 Copy**

1 999

**样例输出 Copy**

链接：[XP的素数][XP]

## 代码 ##

import java.util.Scanner;
    
    public class Main { 
    	public static int prime(int n){ 
    		
    		if(n==1)
    			return 0;  //1不是素数，返回0
    		for(int i=2;i<n;i++){ 
    			if(n%i==0)
    				return 0;
    			continue;
    		}
    			
    		return 1;
    	}
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()){ 
    			int m = sc.nextInt();
    			int n = sc.nextInt();
    			int sum = 0;
    			
    			for(int i = m;i<=n-2;i++)
    				if(prime(i)==1&&prime(i+2)==1)
    					sum++;
    			System.out.println(sum);
    		}
    
    	}
    
    }

# B、XP的点滴 #

**题目描述**

*  XP一不留神感冒了，于是跑到校医院打点滴。打点滴真是无聊啊，他看到盐水一滴一滴地滴下来，突然想到一个问题：如果盐水有规律地滴下，先滴一滴，停一下；然后滴二滴，停一下；再滴三滴，停一下…，假设这瓶盐水一共有n毫升，每一滴是y毫升，每一滴需要的时间是一秒（假设最后一滴不到y毫升，需花费的时间也算一秒），停一下的时间也是一秒。请问XP多久能挂完这瓶盐水呢？

**输入**

*  单组输入数据 n y (0<n,y<=1000)

**输出**

*  输出一行结果

**样例输入 Copy**

10 1

**样例输出 Copy**

链接：[XP的点滴][XP 1]

## 代码 ##

import java.util.Scanner;
    
    public class Main { 
    	public static int count(int []c,int n,int y){ 
    		int temp = 0;//记录每次滴落的滴数
    		for(int i=0;i<c.length;i++)//i代表中间间隔几次
    			c[i] = i+1;
    		int sum = 0;//总量的滴数，几滴就几秒
    		double x = n/(y*1.0);
    		if(x>n/y)
    			sum = n/y+1;
    		else
    			sum = n/y;
    		int j = 0;
    		for(int i=0;i<c.length;i++)
    			if(n>0){ 
    				n-=c[i]*y;//记录间断次数
    				j = i;
    			}
    		temp = j+sum;
    		
    		return temp;
    	}
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()){ 
    			int n = sc.nextInt();
    			int y = sc.nextInt();
    			int []c = new int[105];
    			System.out.println(count(c,n,y));
    		}
    	}
    }

# C、今年暑假不AC #

**题目描述**

*  “今年暑假不AC？”
 *  “是的。”
 *  “那你干什么呢？”
 *  “看世界杯呀，笨蛋！”
 *  “@\#$%^&\*%…”

确实如此，世界杯来了，球迷的节日也来了，估计很多ACMer也会抛开电脑，奔向电视了。  
作为球迷，一定想看尽量多的完整的比赛，当然，作为新时代的好青年，你一定还会看一些其它的节目，比如新闻联播（永远不要忘记关心国家大事）、非常6+7、超级女生，以及王小丫的《开心辞典》等等，假设你已经知道了所有你喜欢看的电视节目的转播时间表，你会合理安排吗？（目标是能看尽量多的完整节目）

**输入**

*  输入数据包含多个测试实例，每个测试实例的第一行只有一个整数n(n<=100)，表示你喜欢看的节目的总数，然后是n行数据，每行包括两个数据Ti\_s,Ti\_e  
    (1<=i<=n)，分别表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。n=0表示输入结束，不做处理。

**输出**

*  对于每个测试实例，输出能完整看到的电视节目的个数，每个测试实例的输出占一行。

**样例输入 Copy**

12
    1 3
    3 4
    0 7
    3 8
    15 19
    15 20
    10 15
    8 18
    6 12
    5 10
    4 14
    2 9
    0

**样例输出 Copy**

链接：[今年暑假不AC][AC]

## 代码 ##

import java.util.Scanner;
    
    public class Main { 
    	
    	public static void swap(int[][] a,int j){ 
    		int temp = a[j][1];
    		a[j][1] = a[j+1][1];
    		a[j+1][1] = temp;
    		
    		temp = a[j][0];
    		a[j][0] = a[j+1][0];
    		a[j+1][0] = temp;
    	}
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()){ 
    			int n = sc.nextInt();
    			if(n<=0)
    				break;
    			
    			int [][]a = new int[n][2];
    			for(int i=0;i<n;i++){ 
    				a[i][0] = sc.nextInt();
    				a[i][1] = sc.nextInt();
    			}
    			
    			for(int i=0;i<n-1;i++)
    				for(int j=0;j<n-1-i;j++)
    					if(a[j][1]>a[j+1][1])
    						swap(a,j);
    			
    			int count = 1;
    			int num = a[0][1];
    			for(int i=1;i<n;i++)
    				if(a[i][0]>=num){ 
    					num = a[i][1];
    					count++;
    				}
    			System.out.println(count);
    		}
    	}
    }

# D、最优装载 #

**题目描述**

*  使用贪心算法求解最优装载问题。

**输入**

*  每组输入包括两部分， 第一行包括集装箱个数n，以及船的装载量C。 接下来n行每行则输入集装箱编号以及其重量。

**输出**

*  输出包括两行，第一行为最多可装载的集装箱数量 。 第二行则为最优装载方案对应的所有集装箱编号（按照装载次序输出，用空格隔开） 。

**样例输入 Copy**

5 10
    1 1
    2 2
    3 3
    4 4
    5 5

**样例输出 Copy**

4
    1 2 3 4

## 代码 ##

链接：[最优装载][Link 1]

import java.util.Scanner;
    
    public class Main { 
    	
    	public static void swap(int[][] a,int j){ 
    		int temp = a[j][1];
    		a[j][1] = a[j+1][1];
    		a[j+1][1] = temp;
    		
    		temp = a[j][0];
    		a[j][0] = a[j+1][0];
    		a[j+1][0] = temp;
    	}
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()){ 
    			int n = sc.nextInt();
    			int c = sc.nextInt();
    			if(n<=0)
    				break;
    			
    			int [][]a = new int[n][2];
    			for(int i=0;i<n;i++){ 
    				a[i][0] = sc.nextInt();//编号
    				a[i][1] = sc.nextInt();//重量
    			}
    			
    			for(int i=0;i<n-1;i++)
    				for(int j=0;j<n-1-i;j++)
    					if(a[j][1]>a[j+1][1])
    						swap(a,j);
    			
    			int count = 0;
    			int x[] = new int[n];
    			for(int i=0;i<n;i++)
    				if(a[i][1]<=c){ 
    					c-=a[i][1];
    					count++;
    					x[i] = a[i][0];
    				}
    			System.out.println(count);
    			for(int i=0;i<count;i++)
    				System.out.print(x[i]+" ");
    			System.out.println();
    		}
    	}
    }

# E、XP的小视频 #

**题目描述**

*  XP的表哥为他推荐了一些学习计算机编程的小视频，这些视频的播放时间长短不完全相同。现在给定一段时间，你能告诉XP他最多可以看多少个视频吗？每个视频的播放时间和给定的总时间均用分钟为单位。

**输入**

*  单组输入数据 第一行为m n ，m为给定时间长度（分钟）(0<n,m<=1000) ，n表示视频个数 ，接下来是n个整数代表每个视频的播放时间(每个视频播放时间为不超过1000的正整数)

**输出**

*  输出一个整数代表XP最多可以看的视频数。

**样例输入 Copy**

84 6
    65 46 18 76 79 3

**样例输出 Copy**

## 代码 ##

import java.util.Arrays;
    import java.util.Scanner;
    
    public class Main { 
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()){ 
    			int m = sc.nextInt();//给定时间长度
    			int n = sc.nextInt();//视频个数
    			int a[] = new int[n];
    			for(int i=0;i<n;i++)
    				a[i] = sc.nextInt();
    			Arrays.sort(a);//排序，按视频长度从小到大
    			int count = 0;
    			for (int i=0;i<n&&a[i]<=m;i++) { 
    	              m -= a[i];//更新总重量
    	              ++count;
    	        }
    			System.out.println(count);
    	   }
    	}
    }

# F、最小生成树（Prim） #

**题目描述**

*  使用Prim算法求图的最小生成树(MST)

**输入**

*  每组数据分为两个部分，第一部分为图的点数n，和边数m, 第二部分为m行，每一行输入三个数字，前两个为两个顶点的编号，第三个为边权重。

**输出**

*  最小生成树，输出时按照边的两个端点的升序输出。（先看左端点，再看右端点，端点不换位置）

**样例输入 Copy**

3 3
    0 1 10
    0 2 15
    1 2 50

**样例输出 Copy**

0 1 10
    0 2 15

## 代码 ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int MAXN = 1010;
    const int INF = 0x3f3f3f3f;
    
    int n,m;
    int G[MAXN][MAXN];
    int g[MAXN][MAXN];
    void init(){ 
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                G[i][j]=INF;
    }
    
    struct Edge{ 
        int lp;
        int rp;
        int len;
    };
    
    int cmp(const Edge &a,const Edge &b){ 
        if(a.lp==b.lp) return a.rp<b.rp;
        return a.lp<b.lp;
    }
    
    int main(){ 
        while(cin>>n>>m){ 
            Edge edges[m];
            init();
            int x,y,z,cnt=0;
            for(int i=0;i<m;i++){ 
                cin>>x>>y>>z;
                G[y][x]=z;
                G[x][y]=z;
                g[x][y]=z;
            }
            int closeset[MAXN],lowcost[MAXN],used[MAXN];
            for(int i=0;i<n;i++){ //初始化
                lowcost[i]=G[0][i];
                closeset[i]=0;
                used[i]=0;            
            }
            used[0]=1;
            for(int i=1;i<n;i++){ //每一次循环，找出一个到S最近的顶点
                int j=0;
                for(int k=0;k<n;k++){ 
                    if((!used[k])&&(lowcost[k]<lowcost[j]))//k点不在S里面
                        j=k;
                }
                if(g[closeset[j]][j]==lowcost[j]){ 
                    edges[cnt].lp=closeset[j];
                    edges[cnt].rp=j;
                    edges[cnt].len=lowcost[j];
                }
                else{ 
                    edges[cnt].lp=j;
                    edges[cnt].rp=closeset[j];
                    edges[cnt].len=lowcost[j];
                }
                cnt++;
                used[j]=1;
                for(int k=0;k<n;k++){ 
                    if((!used[k])&&(G[j][k]<lowcost[k])){ 
                        lowcost[k]=G[j][k];
                        closeset[k]=j;
                    }
                }
            }
            sort(edges,edges+cnt,cmp);
            for(int k=0;k<cnt;k++){ 
                printf("%d %d %d\n",edges[k].lp,edges[k].rp,edges[k].len);
            }
        }
        return 0;
    }

Java代码：

import java.util.Arrays;
    import java.util.Scanner;
    
    public class Main { 
    	public static int n;
    	public static int [][]c = new int[1000][1000];
    	 
    	public static void prim(int n){ 
    		class Edge implements Comparable{ 
    			int u,v,w;//这个类用来存边
    			public Edge(int u,int v,int w){ 
    				this.u = u;
    				this.v = v;
    				this.w = w;
    			}
    
    			@Override
    			public int compareTo(Object o) { //重写排序规则
    				// TODO Auto-generated method stub
    				Edge edge = (Edge)o;
    				if(edge.u!=this.u)
    					return this.u-edge.u;
    				return this.v-edge.v;
    			}
    			
    		}
    		Edge e[] = new Edge[n-1];
    		float []lowcost = new float[n+1];//最短距离
    		int []closest = new int[n+1];//邻居
    		boolean []s = new boolean[n+1];//顶点是否被访问
    		
    		s[1] = true;
    		for(int i=2;i<=n;i++){ 
    			lowcost[i] = c[1][i];
    			closest[i] = 1;
    			s[i] = false;
    		}
    		
    		for(int i=1;i<n;i++){ 
    			float min = Float.MAX_VALUE;
    			int j = 1;
    			for(int k=2;k<=n;k++)
    				if((lowcost[k]<min)&&(!s[k])){ 
    					min = lowcost[k];
    					j = k;
    				}
    			if(c[closest[j]][j]>0)//先存下来
    			    e[i-1] = new Edge((closest[j]-1),(j-1),c[closest[j]][j]);
    			else
    				e[i-1] = new Edge((j-1),(closest[j]-1),(-1)*c[closest[j]][j]);
    			
    			s[j] = true;
    			for(int k=2;k<=n;k++)
    				if((c[j][k]<lowcost[k])&&(!s[k])){ 
    					lowcost[k] = Math.abs(c[j][k]);
    					closest[k] = j;
    				}
    			
    		}
    		//开始处理结果集
    		Arrays.sort(e);
    		for(int i=0;i<n-1;i++){ 
    			Edge x = e[i];
    			System.out.println(x.u+" "+x.v+" "+x.w);
    		}
    	}
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()){ 
    			int n = sc.nextInt();//点数
    			int m = sc.nextInt();//边数
    			for(int i=1;i<=n;i++)
    	            for(int j=1;j<=n;j++)
    	                c[i][j] = 10000;
    			
    			for(int i=1;i<=m;i++){ 
    	            int x = sc.nextInt();
    	            int y = sc.nextInt();
    	            int z = sc.nextInt();
    	            ++x;
    	            ++y;
    	            c[x][y]=z;
    	            c[y][x]=-1*z;
    	        }
    			prim(n);
    		}
    	}
    }

> 【今天下午吃了广东鱼粉，学校食堂的，不知道正不正宗，反正我挺喜欢的，嘿嘿~】  
> 句子君：
> 
> > “这是一个长满了百合花的峡谷。百合花静静地开放着，水边、坡上、岩石旁、大树下，到处都有。它们不疯不闹，也无鲜艳的颜色，仿佛它们开放着，也就是开放着，全无一点别的心思。峡谷上空的阳光是明亮的，甚至是强烈的，但因为峡谷太深，阳光仿佛要走过漫长的时间。因此，照进峡谷，照到这些百合花时，阳光已经变得柔和了，柔和得像薄薄的、轻盈得能飘动起来的雨幕。”  
> > ——曹文轩《根鸟》

[XP]: https://blog.csdn.net/qq_42766201/article/details/84783468
[XP 1]: https://blog.csdn.net/qq_46546793/article/details/105853500
[AC]: https://blog.csdn.net/qq_46621935/article/details/109554202
[Link 1]: https://blog.csdn.net/ZHANGQIANYI2020/article/details/112511176