題意:對于題目給的點,x固定,而與x組合的y可以任意交換,求如何安置y可使這些點組成線段下面的面積最大,最大面積是多少
分析:可以發現Xn-Xn-1的越大那么乘以y越大,所以我們只需求出,然后ΔX越大的數和y越大的數相乘在除以2就是結果,通過畫圖很容易得出結論
? ? ? ? ?但是還有一個問題就是,對于i=0,i=n-1,Yi只乘以了一遍,而對于0<i<n的區間,每個Yi都乘以了兩遍
? ? ? ? ?所以在求ΔX時候,當i=0,ΔX=X1-X0,當i=n-1時,ΔX=Xn-1-Xn-2,而對于0<i<n,ΔX=Xi+1-xi-1;
? ? ? ? ?這樣就能確保每個y每個都可以被乘以了兩次。
? ? ? ? ?(對于兩邊的區間Y不僅被乘以了1次,而且是最小的兩個值放在了兩邊)
#include<stdio.h> #include < string .h> #include <math.h> #include <algorithm> using namespace std; const int MN= 1100 ; double x[MN],y[MN],r[MN]; bool cmp( double a, double b) { return a< b; } int main() { int i,j,n; double sum; int T; scanf( " %d " ,& T); while (T-- ) { sum = 0 ; scanf( " %d " ,& n); for (i= 0 ;i<n;i++ ) scanf( " %lf%lf " ,&x[i],& y[i]); sort(x,x + n,cmp); sort(y,y + n,cmp); for (i= 0 ;i<n- 1 ;i++ ) { if (i== 0 ) r[i]=x[i+ 1 ]- x[i]; else r[i]=x[i+ 1 ]-x[i- 1 ]; } r[i] =x[i]-x[i- 1 ]; sort(r,r + n,cmp); for (i= 0 ;i<n;i++ ) { sum +=r[i]* y[i]; } printf( " %.1lf\n " ,sum/ 2 ); } return 0 ; }
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
