codeforces div2 C题思路训练【C题好难，我好菜】

时间：2023-01-03 15:57:24

1017C The Phone Number:

构造数列使得LIS和LDS的和最小，定理已知LIS=L，LDS=n/L的向上取整，根据样例可以得到设置L=根号n，构造方法如样例

截断法构造，不用考虑边界：

Show an example of n=22:

"' 19 20 21 22 15 16 17 18 11 12 13 14 7 8 9 10 3 4 5 6 1 2 "'

 　　 int tmp = sqrt(n);

     for(int i=,j,o=n;i<=n;i+=tmp)

     {

         for(j=min(i+tmp-,n);j>=i;a[j--]=o--);

     }

1019A Elections:

选举投票，收买投票人使得1号获胜的最少金额，本题容易陷入样例的坑里而无法自拔。正确做法观察输入规模3000，时间1s，那就枚举咯

 int n,m,a[],b[],x[],c[];

 L p=1e18;

 int main()

 {

     int i,j;

     L k;

     scanf("%d%d",&n,&m);

     for(i=;i<=n;i++)

       scanf("%d%d",&a[i],&b[i]);

     for(i=;i<=n;i++) // 两个数组的选择排序

       for(j=i+;j<=n;j++)

         if(b[i]>b[j])

           swap(a[i],a[j]),swap(b[i],b[j]);

     for(i=;i<=n;i++) // 枚举所有的次小值i
     {

        k=;

        for(j=;j<=m;j++)

          x[j]=;

        for(j=;j<=n;j++)

          c[j]=;

        for(j=n;j>;j--) // 从后向前

          if(x[a[j]]<i || a[j]==)

            x[a[j]]++;

          else

            k+=b[j],c[j]=,x[]++; // 超过阈值的，都买入

        for(j=;j<=n;j++) // 能买的再过一遍

          if(x[]<=i && a[j]!= && c[j]==)

            k+=b[j],c[j]=,x[]++;

        if(x[]>i)

          p=min(p,k);

     }

     cout<<p;

     return ;

 }

相关文章