设为首页 加入收藏

TOP

Codeforces Round #251 (Div. 2) D 二分
2015-07-20 18:00:11 来源: 作者: 【大 中 小】 浏览:1次
Tags：Codeforces Round #251 Div. D二分

?

是个不错的题目，首先多画几个不难发现，若要满足题目条件有可能 a数组的最小值要不断增大，也有可能b数组的最大值不断减小，一开始直接用了优先队列，发现了不对的地方，因为没一次 有两个情况 要么a加要么b减，所以不能直接来，多画几个不难发现，我们需要找到一个值 x是的 a中所有元素都大于等于x，而b中所有元素都小于等于x,所以只需要找到这个x即可，根据多画了几个的情况 发现x应该是 在a跟b中的元素之一，所以多画了几个发现都正确，那么直接在a,b数组中暴力查找，然后再进行二分查找答案，然后获得最终最小的那个答案，求答案需要维护一下 a的前缀和 与b的后缀和 即可

?

?

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 #define ll long long #define eps 1e-8 const int inf = 0xfffffff; const ll INF = 1ll<<61; using namespace std; //vector
                
                  > G; //typedef pair
                 
                   P; //vector
                  
                    > ::iterator iter; // //map
                   
                    mp; //map
                    
                     ::iterator p; int n,m; ll ans; ll aa[100000 + 55],bb[100000 + 55]; ll sa[100000 + 55],sb[100000 + 55]; vector
                     
                       G; void init() { memset(aa,0,sizeof(aa)); memset(bb,0,sizeof(bb)); memset(sa,0,sizeof(sa)); memset(sb,0,sizeof(sb)); G.clear(); } bool input() { while(scanf(%d %d,&n,&m) == 2) { for(int i=1;i<=n;i++) {scanf(%I64d,&aa[i]);G.push_back(aa[i]);} for(int i=1;i<=m;i++) {scanf(%I64d,&bb[i]);G.push_back(bb[i]);} return false; } return true; } ll find(ll x) { ll sum = 0; int pos = lower_bound(aa + 1,aa + n + 1,x) - aa; sum += (pos - 1) * x - sa[pos - 1]; pos = lower_bound(bb + 1,bb + m + 1,x) - bb; sum += sb[pos] - (m - pos + 1) * x; return sum; } void cal() { sort(aa + 1,aa + n + 1); sort(bb + 1,bb + m + 1); sort(G.begin(),G.end()); for(int i=1;i<=n;i++)sa[i] = sa[i - 1] + aa[i]; for(int i=m;i>0;i--)sb[i] = sb[i + 1] + bb[i]; ans = INF; for(int i=0;i
                      
                       
?

                       
?
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：HDU 2294 Pendant （DP+矩阵快速.. 下一篇：HDU 2256 Problem of Precision ..

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: