code forces 1176 D. Recover it!

原题链接:https://codeforces.com/contest/1176/problem/D

本文链接:https://www.cnblogs.com/blowhail/p/11146761.html

题目大意是 两个个数列 a , b 相同 ,如果 ai 是素数,那么b数列里添加上第ai个素数(2为第一个),如果不是素数,那么b数列里添加上ai的最大因子。现在给出添加完之后的b数列,求出a数列。

大致思路: 先从大到小排序,然后判断是不是素数,如果是素数,那就遍历一遍,找到它是第几个素数,然后输出并记录下来。  如果不是素数,就直接输出,再求出最大的因子记录下来。

写超时了好多次,修改了很多地方,可读性估计不太好

 

代码如下

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#define ll long long
#define pi 3.1415926
using namespace std;
int primes[200006],a[400005],b[3000005],p2[3000005];
//这里primes数组按顺序记录素数,p2是 素数为1 非素数为0
//a数组是存下输入的数列,b数组是记录每个数的个数 bool cmp (int x,int y) { return x>y; } void prime (int n) { int i,t, k,j; primes[1]=2; p2[2]=1; int f,p=2; for (i=3;i<=n;++i){ k=sqrt(i); f=1; for (t=2;t<=k;++t) if(i%t==0) { f=0; break; } if (f){ primes[p++]=i; //按顺序存 p2[i]=1; // } } } int main () { int i,t,m,n,l,k,j,p; scanf("%d",&n); j=2*n; for(i=0;i<j;++i){ scanf("%d",&a[i]); b[a[i]]++; //记录每个数个数 } sort(a,a+j,cmp); prime(a[0]); int c=200000; //这里我用c来记录每次遍历素数的位置,然后下一次就直接从这个位置继续遍历(因为已经从大到小排序了) for (i=0;i<j;++i) { if (b[a[i]]==0) continue; if (p2[a[i]]==1){ for (int h=c;h>=1;--h) if (primes[h]==a[i]){ c=h; break; }
         printf("%d ",c);
        b[ a[i] ]--;  
            b[c]--;       //b是记录每个数出现次数,每次遍历完都把找出来的数给减去
        }
        else
        {
            printf("%d ",a[i]);
            for (int h=2;h<a[i];++h)
                if (a[i]%h==0)
            {
                k=a[i]/h;
                break;
            }
            b[a[i]]--;
            b[k]--;
        }
    }
    printf("\n");
    return 0;
}

 

上一篇:[kuangbin带你飞]专题十二 基础DP1 G - 免费馅饼 HDU - 1176


下一篇:1176:谁考了第k名