首页 > 代码库 > codeforces 289B - Polo the Penguin and Matrix 二分+dp

codeforces 289B - Polo the Penguin and Matrix 二分+dp

2024-07-14 19:14:26   219人阅读

题意：给你一个序列，每一次可以对序列里面任意数+d 或者 -d 问你最少多少步能够使得数列里面所有的数相等

解题思路：从 1 - 10000 枚举这个数，二分找数列中小于等于它的最大的那个数，然后求前缀和以后刻意快速求出差值和的绝对值，差值和/d 就是我们所求数。

解题代码：

 1 // File Name: 289b.cpp 2 // Author: darkdream 3 // Created Time: 2014年07月29日 星期二 22时33分11秒 4  5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<stack>11 #include<bitset>12 #include<algorithm>13 #include<functional>14 #include<numeric>15 #include<utility>16 #include<sstream>17 #include<iostream>18 #include<iomanip>19 #include<cstdio>20 #include<cmath>21 #include<cstdlib>22 #include<cstring>23 #include<ctime>24 25 using namespace std;26 int a[10005];27 int sum[10005];28 int n , m ,d; 29 int find(int x)30 {31     int l = 1, r = n;32     while(l <= r)33     {34         int m = (l+r)/2;35         if(a[m] > x)36         {37             r = m -1; 38         }else {39             l = m + 1; 40         }41     }42     return r; 43 }44 int main(){45     scanf("%d %d %d",&n,&m,&d);46     n = n * m ;47     sum[0] = 0 ; 48     for(int i = 1;i <= n ;i ++)49     {50         scanf("%d",&a[i]);51     }52     sort(a+1,a+1+n);53     int M = 1e9 ; 54     int ok = 1;55     sum[1] = a[1];56     for(int i = 2;i <= n;i ++)57     {58         sum[i] = sum[i-1] + a[i];59         if((a[i]-a[i-1])%d != 0 )60             ok = 0; 61     }62     if(ok)63     {64         ok = 0; 65         for(int i = 1 ;i <= 10000;i ++)66         {67             int k =  find(i);68             if(k == 0 )69                 continue;70             int ans = i*k - sum[k]  +(sum[n]-sum[k] -(n-k)*i);71             if( ans%d == 0 && ans/d <= M)72             {73                 M = ans/d;74             //    printf("%d %d %d %d\n",ans,i,k,M);75                 ok = 1; 76             }77         }78     }79     if(ok  ==1  )80         printf("%d\n",M);81     else printf("-1\n");82 83 84     return 0;85 }
View Code

 


联系
我们