題目鏈接：http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1005&cid=779

題目大意：在一個(gè)二維坐標(biāo)網(wǎng)格里畫線，可以畫一條長(zhǎng)度為1的邊或者長(zhǎng)度為根號(hào)2的對(duì)角線。給一個(gè)面積S，問至少需要多少畫才能得到一個(gè)面積大于S的區(qū)域。

關(guān)鍵思想：貪心嘛，在周長(zhǎng)一定的情況下 ，為了得到最大面積，一定要越接近正方形越好，并且一定是凸多邊形。不然的話，找到凹邊兩邊連起來得到一條對(duì)稱軸，凹邊對(duì)稱之后得到的凸多邊形周長(zhǎng)相同，面積更大。

然后我們就開始考慮邊長(zhǎng)為2根號(hào)2的正方形，我們對(duì)這個(gè)正方形加邊進(jìn)行擴(kuò)展，加一條邊產(chǎn)生一個(gè)小梯形；再加一條邊變成一個(gè)長(zhǎng)方形，邊長(zhǎng)之差為根號(hào)2；再在較短邊那里加一條邊變成長(zhǎng)的小梯形；再加一條邊變成新的正方形，邊長(zhǎng)比最初的大了根號(hào)2，這就構(gòu)成一個(gè)循環(huán)。需要注意的是，如果邊長(zhǎng)為根號(hào)2，則無法加邊構(gòu)成小梯形，需要特判。

代碼預(yù)處理了數(shù)組，再用二分查找，0msAC。

代碼如下：

#include<iostream> #include<cstdio> #include<cstring> #include<string> using namespace std; #define MAX 100010 int a[MAX]; int main() {for(int i=0;i<4;i++)a[i] = 0;a[4] = 2;a[5] = 2;a[6] = 4;a[7] = 5;for(int i=8;i<MAX;i++){if(i%4==1)a[i] = (i/4) -1 + a[i-1];else if(i%4==2)a[i] = 2*(i/4) + a[i-2];else if(i%4==3)a[i] = 3*(i/4) + a[i-3];else if(i%4 == 0)a[i] = (i/4)*(i/4)*2;}int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);if(n==0){cout<<"0"<<endl;continue;}int left = 0,right = MAX-1;int mid = (left+right)/2;while(left<right){if(a[mid] < n)left = mid+1;elseright = mid;mid = (left+right)/2;}cout<<left<<endl;}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/G-M-WuJieMatrix/p/7398213.html

總結(jié)

以上是生活随笔為你收集整理的2017中国大学生程序设计竞赛 - 网络选拔赛 [1005 - CaoHaha's staff] 贪心的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。