HDU 6651 Final Exam-白红宇

HDU 6651 Final Exam

阅读量：4493 次

发布时间：2019-06-08

本文共 931 字，大约阅读时间需要 3 分钟。

题意：n个数字未知，总和为m，问最少怎么填数字，使得必定有k个数比原序列中的大

a：？？？？？ sum=m

b：b1 b2 b3 b4 b5 count( b [ i ] > a [ i ] ) >=k （b填数字

a是万能视角，能任意采取排数策略，假设a知道b的排列

考虑田忌赛马的策略，若a不想让b赢，则至少让k-1个0与b的前k-1大去比，那么b有k-1个符合条件，a只要让b中剩下的（n-（k-1））个数都小于a中剩下的数就好了

即 a中的数最大可取 m / ( n - ( k-1 ) ) +1

反过来只要让b中k-1个数取m / ( n - ( k-1 ) ) +1，为了确保符合条件，剩下一个数最少取 m+1, 其余取0，那么就一定有k个数符合条件

这样当a取最优策略，k-1个0与b中前k-1大的数去比，b就有k-1个数符合条件，b中剩下的第k小的数一定会比a中某一个数大，即有k个数符合条件

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 using namespace std;typedef long long ll;typedef pair
                 
                   P;typedef long double ld;#define mem(x) memset(x, 0, sizeof(x))#define me(x) memset(x, -1, sizeof(x))#define fo(i,n) for(i=0; i
                  
                   >t; while(t--) { cin>>n>>m>>k; cout<<(1+m/(n-k+1))*(k-1)+m+1<

转载于:https://www.cnblogs.com/op-z/p/11342543.html

你可能感兴趣的文章

Codeforces Round #FF (Div. 2) D. DZY Loves Modification 优先队列