官方提供的解题报告:http://codeforces.com/blog/entry/4808
Problem В(div 1)/D(div 2) — Guess That Car!
We need to find such x and y that
the value of is
minimum possible. This expression can be rewritten as .
Note that the first part doesn’t depend on y and the second part doesn’t depend on x,
so we can minimize these parts separately. Here is how to minimize ,
the second part is minimized similarly. As the expression in the brackets doesn’t depend on j, this part can be rewritten as ,
where .
Now it’s enough to calculate the required value for all possible values of x and choose x for
which this value is the smallest. The optimal value of y can be found similarly.
The overall complexity of this solution is O(n·m + n2 + m2).
As the objective function is convex, other approaches to this problem are possible, for example, ternary search, gradient descent or analytical approach (calculation of derivatives).
AC CODE:
//Memory: 5400 KB Time: 390 MS //Language: GNU C++ 4.6 Result: Accepted #include <iostream> #include <cstdio> #define MAXN 1001 using namespace std; int car[MAXN][MAXN]; long long si[MAXN] = {0}, sj[MAXN] = {0}; //要设为long long才能过 int main() { int n, m, li, lj; long long sumx, sumy; scanf("%d %d", &n, &m); //注意,(i,j)对应car[j][i] //行号:y轴 for(int j = 1; j <= n; j++) { //列号:x轴 for(int i = 1; i <= m; i++) { scanf("%d", &car[j][i]); si[i] += car[j][i]; sj[j] += car[j][i];//cout<<1; } } //for(int i = 1; i <= m; i++) cout<<si[i]<<" "; //for(int i = 1; i <= n; i++) cout<<sj[i]<<" "; sumx = sumy = 9223372036854775807; //处理x //第一重for loop控制x,第二层控制xi for(int x = 0; x <= 4*m; x += 4) { long long tmp = 0; for(int i = 1; i <= m; i++) { tmp = tmp + si[i]*(x - 4*i + 2)*(x - 4*i + 2); } if(tmp < sumx) { sumx = tmp; lj = x/4; } } //处理y //第一重for loop控制y,第二层控制yj for(int y = 0; y <= 4*n; y += 4) { long long tmp = 0; for(int j = 1; j <= n; j++) { tmp = tmp + sj[j]*(y - 4*j + 2)*(y - 4*j + 2); //cout<<"" } if(tmp < sumy) { sumy = tmp; li = y/4; } } //cout<<sumx<<" "<<sumy<<endl; printf("%I64dn%d %dn", sumx + sumy, li, lj); return 0; }
原文链接: https://www.cnblogs.com/cszlg/archive/2012/08/08/2910569.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/58569
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!