[编程题]素数伴侣
- 热度指数：190919 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
第一行输入一个正偶数
代表数字个数。
个正整数
代表给定的数字。
输出描述:
示例1
输入
4 2 5 6 13
输出
2
说明
和
可以组成一对素数伴侣，
和
也可以组成一对素数伴侣。因此，最多可以挑选出
示例2
输入
4 1 2 2 2
输出
1
说明
只能使用一次，与任意一个
示例3
输入
2 3 6
输出
0
package main
import (
"fmt"
)
func isPrime(n int) bool {
if n < 2 {
return false
}
for i := 2; i*i <= n; i++ {
if n%i == 0 {
return false
}
}
return true
}
func getMax(nums []int) int {
res := 0
// 按奇偶划分
odds := []int{}
evens := []int{}
for i := 0; i < len(nums); i++ {
if nums[i]&1 == 1 {
odds = append(odds, nums[i])
} else {
evens = append(evens, nums[i])
}
}
n := len(evens)
// 为每个奇数寻找匹配的偶数
// 采用的策略：先到先得, 能让则让
// 先到先得：如果该偶数的匹配为0，就直接与之匹配
// 能让则让：如果该偶数已经匹配(匹配不为零)，那么为与之匹配的奇数重新寻找匹配，如果能找到新的匹配，那么就把该偶数让给当前奇数
// 否则该奇数不能找到匹配
visited := make([]bool, n) //记录第i个偶数在本轮匹配中是否被访问过
matched := make([]int, n) //记录与第i个偶数匹配的奇数
var match func(int) bool //检查该奇数是否能找到合适的匹配, 注意：这是一个闭包函数
match = func(odd int) bool {
for i := 0; i < n; i++ {
if isPrime(odd+evens[i]) && !visited[i] {
visited[i] = true
if matched[i] == 0 || match(matched[i]) {
matched[i] = odd
return true
}
}
}
return false
}
// 为每个奇数寻找匹配
// 每轮的 visited 要清空
for _, odd := range odds {
visited = make([]bool, n)
if match(odd) {
res++
}
}
return res
}
func main() {
var n int
fmt.Scanf("%d", &n)
nums := make([]int, n)
for i := 0; i < n; i++ {
fmt.Scanf("%d", &nums[i])
}
fmt.Println(getMax(nums))
}
发表于 2022-08-17 09:56:11
回复(0)
GO语言实现 匈牙利算法
package main
import "fmt"
import "io"
import "math"
func main(){
for {
var n int
var num int
var odds []int
var evens []int
c, err := fmt.Scanf("%d\n", &n)
if c==0 || err==io.EOF{
break
}
for i:=0; i<n; i++{
fmt.Scanf("%d", &num)
if num % 2 == 0{
evens = append(evens, num)
}else{
odds = append(odds, num)
}
}
var suited map[int]int = make(map[int]int)
var K int
for i:=0; i<len(odds); i++{
var visited map[int]int = make(map[int]int)
ok := match(odds[i], evens, visited, suited)
if ok {
K++
}
}
fmt.Println(K)
}
}
func match(odd int, evens []int, visited map[int]int, suited map[int]int) bool {
for _, even := range evens{
if isPrime(odd + even) && visited[even] == 0 {
visited[even] = 1
if suited[even] == 0 || match(suited[even], evens, visited, suited) {
suited[even] = odd
return true
}
}
}
return false
}
func isPrime(num int) bool {
n := math.Sqrt(float64(num))
n2 := int(n + 0.5)
for i := 2; i <= n2; i++{
if num%i == 0{
return false
}
}
return true
}
发表于 2022-01-06 23:16:43
回复(0)
package main
import (
"bufio"
"fmt"
"math/big"
"os"
"strconv"
"strings"
)
func main() {
scan := bufio.NewScanner(os.Stdin)
for {
scan.Scan()
nums := scan.Text()
if nums == "" {
break
}
numsList := strings.Split(nums, " ")
if len(numsList) == 1 {
continue
}
numList := make([]int, 0, len(numsList))
for _, v := range numsList {
num, _ := strconv.Atoi(v)
numList = append(numList, num)
}
ji, ou := GroupList(numList)
result := 0
match := make([]int, len(ou))
for i:= 0; i < len(ji); i ++ {
used := make([]int, len(ou))
if find(ji[i], used, match, ou) {
result ++
}
}
fmt.Println(result)
}
}
// 分奇偶
func GroupList(n []int) ([]int, []int) {
odd := make([]int, 0, len(n))
even := make([]int, 0, len(n))
for _, v := range n {
if v %2 == 1 {
odd = append(odd, v)
continue
}
even = append(even, v)
}
return odd, even
}
func find(x int, l1, l2, l3 []int) bool {
for i := 0; i < len(l3); i ++ {
if big.NewInt(int64(l3[i] + x)).ProbablyPrime(0) && l1[i] == 0 {
l1[i] = 1
if l2[i] == 0 || find(l2[i], l1, l2, l3) {
l2[i] = x
return true
}
}
}
return false
}
import (
"bufio"
"fmt"
"math/big"
"os"
"strconv"
"strings"
)
func main() {
scan := bufio.NewScanner(os.Stdin)
for {
scan.Scan()
nums := scan.Text()
if nums == "" {
break
}
numsList := strings.Split(nums, " ")
if len(numsList) == 1 {
continue
}
numList := make([]int, 0, len(numsList))
for _, v := range numsList {
num, _ := strconv.Atoi(v)
numList = append(numList, num)
}
ji, ou := GroupList(numList)
result := 0
match := make([]int, len(ou))
for i:= 0; i < len(ji); i ++ {
used := make([]int, len(ou))
if find(ji[i], used, match, ou) {
result ++
}
}
fmt.Println(result)
}
}
// 分奇偶
func GroupList(n []int) ([]int, []int) {
odd := make([]int, 0, len(n))
even := make([]int, 0, len(n))
for _, v := range n {
if v %2 == 1 {
odd = append(odd, v)
continue
}
even = append(even, v)
}
return odd, even
}
func find(x int, l1, l2, l3 []int) bool {
for i := 0; i < len(l3); i ++ {
if big.NewInt(int64(l3[i] + x)).ProbablyPrime(0) && l1[i] == 0 {
l1[i] = 1
if l2[i] == 0 || find(l2[i], l1, l2, l3) {
l2[i] = x
return true
}
}
}
return false
}
发表于 2021-09-01 18:35:04
回复(0)
问题信息
难度：
3条回答
4502收藏
58204浏览
通过挑战的用户
查看代码-
2023-03-10 17:24:29
-
2023-02-05 00:00:38 -
2022-09-17 18:31:04 -
2022-09-16 15:28:02 -
2022-09-16 15:04:19
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <limits.h> #include <math.h> #include <algorithm> #include <vector> using namespace std; vector<int> G[105]; bool flag[105]; int pre[105]; bool dfs(int k){ int x; for(int i=0;i<G[k].size();i++){ x=G[k][i]; if (flag[x]) continue; flag[x]=true; if((pre[x]==0)||dfs(pre[x])){ pre[x]=k; return true; } } return false; } bool isprime[80000]; int nums[105]; int main(){ memset(isprime,1,sizeof(isprime)); isprime[0]=isprime[1]=false; for(int i=4;i<80000;i+=2)isprime[i]=false; for(int i=3;i*i<80000;i+=2) if(isprime[i]){ for(int j=i*i;j<80000;j+=2*i) isprime[j]=false; } int n; while(~scanf("%d",&n)){ for(int i=1;i<=n;i++){ scanf("%d",&nums[i]); } for(int i=1;i<=n;++i){ for(int j=i+1;j<=n;++j){ if(isprime[nums[i]+nums[j]]){ (nums[i]&1)?G[i].push_back(j):G[j].push_back(i); } } } memset(pre,0,sizeof(pre)); int ans=0; for(int i=1;i<=n;i++){ memset(flag,false,sizeof(flag)); if (dfs(i)) ans++; } printf("%d\n",ans); for(int i=1;i<=n;++i){ G[i].clear(); } } return 0; }#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> using namespace std; const int N=510; int n,m,x,y;vector<int>g[N]; namespace Blossom{ int mate[N],n,ret,nxt[N],f[N],mark[N],vis[N];queue<int>Q; int F(int x){return x==f[x]?x:f[x]=F(f[x]);} void merge(int a, int b){f[F(a)]=F(b);} int lca(int x, int y){ static int t=0;t++; for(;;swap(x,y)) if(~x){ if(vis[x=F(x)]==t) return x;vis[x]=t; x=mate[x]!=-1?nxt[mate[x]]:-1; } } void group(int a, int p){ for(int b,c;a!=p;merge(a,b),merge(b,c),a=c){ b=mate[a],c=nxt[b]; if(F(c)!=p)nxt[c]=b; if(mark[b]==2)mark[b]=1,Q.push(b); if(mark[c]==2)mark[c]=1,Q.push(c); } } void aug(int s, const vector<int>G[]){ for(int i=0;i<n;++i)nxt[i]=vis[i]=-1,f[i]=i,mark[i]=0; while(!Q.empty())Q.pop();Q.push(s);mark[s]=1; while(mate[s]==-1&&!Q.empty()){ int x=Q.front();Q.pop(); for(int i=0,y;i<(int)G[x].size();++i){ if((y=G[x][i])!=mate[x]&&F(x)!=F(y)&&mark[y]!=2){ if(mark[y]==1){ int p=lca(x,y); if(F(x)!=p)nxt[x]=y; if(F(y)!=p)nxt[y]=x; group(x,p),group(y,p); }else if(mate[y]==-1){ nxt[y]=x; for(int j=y,k,l;~j;j=l)k=nxt[j],l=mate[k],mate[j]=k,mate[k]=j; break; }else nxt[y]=x,Q.push(mate[y]),mark[mate[y]]=1,mark[y]=2; } } } } int solve(int _n, const vector<int>G[]){ n=_n;memset(mate, -1, sizeof mate); for(int i=0;i<n;++i) if(mate[i]==-1)aug(i,G); for(int i=ret=0;i<n;++i)ret+=mate[i]>i; printf("%d\n",ret); //for(int i=0;i<n;i++)printf("%d %d\n",i+1,mate[i]+1); return ret; } } bool isprime[80000]; int nums[105]; int main(){ memset(isprime,1,sizeof(isprime)); isprime[0]=isprime[1]=false; for(int i=4;i<80000;i+=2)isprime[i]=false; for(int i=3;i*i<80000;i+=2) if(isprime[i]){ for(int j=i*i;j<80000;j+=2*i) isprime[j]=false; } while(~scanf("%d",&n)){ for(int i=0;i<n;i++){ scanf("%d",&nums[i]); } for(int i=0;i<n;++i){ for(int j=i+1;j<n;++j){ if(isprime[nums[i]+nums[j]]){ g[i].push_back(j); g[j].push_back(i); } } } Blossom::solve(n,g); for(int i=0;i<n;++i){ g[i].clear(); } } }