首页 > 代码库 > cf B George and Round

cf B George and Round

2024-11-13 15:24:02   202人阅读

题意：输入n，m，下一行为n个数a1<a2<a3......<an；然后再输入m个数b1<=b2<=b3<.....<=bm； 每个ai都必须在b中找到相等的数，找不到可以让比ai的大的数转化为ai，问最少需要添加几个数，使得ai在b都能找到相等的数。

技术分享
 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5  6 int n,m; 7 int a[3010],b[3010]; 8 int vis[3010000]; 9 bool vis1[3000100];10 11 int main()12 {13     while(scanf("%d%d",&n,&m)!=EOF)14     {15         memset(a,0,sizeof(a));16         memset(b,0,sizeof(b));17         for(int i=0; i<n; i++)18         {19             scanf("%d",&a[i]);20         }21         for(int j=0; j<m; j++)22         {23             scanf("%d",&b[j]);24             vis[b[j]]++;25         }26         int ans=0;27         for(int i=0; i<n; i++)28         {29             if(vis[a[i]]) {vis[a[i]]--; vis1[a[i]]=true;}30         }31         for(int i=0; i<n; i++)32         {33            if(!vis[a[i]]&&!vis1[a[i]])34            {35                bool flag=false;36                for(int j=0; j<m; j++)37                {38                    if(b[j]<a[i]) continue;39                    if(vis[b[j]]==0) continue;40                    vis[b[j]]--;41                    flag=true;42                    break;43                }44                if(!flag) ans++;45            }46         }47         printf("%d\n",ans);48     }49     return 0;50 }
View Code

 

cf B George and Round


联系
我们