題目鏈接：點擊查看

題目大意：中文題面

題目分析：一道比賽時寫崩了的模擬，賽后參考別人的代碼，發現原來這個題目可以寫的如此簡單

說會題目，n 只有 500 ，可以 n * n 枚舉每個位置作為起點，對于每個位置而言，可以 6 * 6?去枚舉周圍曼哈頓距離為 3 的點，將其都壓入一個 vector 中然后排序，顯然在城市分配完畢后，選擇權值較大的點作為接下來的工作地點是最優的，接下來模擬每個回合的過程就好了，注意，不需要枚舉回合，因為大量相鄰的回合所提供的貢獻都是相同的，可以將其劃分一下，就能快速計算了

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=510;int a[N][N];int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){int n,x,y;scanf("%d%d%d",&n,&x,&y);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&a[i][j]);int ans=inf;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){vector<int>num;num.push_back(a[i][j]);for(int xx=i-3;xx<=i+3;xx++)for(int yy=j-3;yy<=j+3;yy++){if(xx<=0||yy<=0||xx>n||yy>n)continue;if(abs(xx-i)+abs(yy-j)>3)continue;if(xx==i&&yy==j)continue;num.push_back(a[xx][yy]);}sort(num.begin()+1,num.end(),greater<int>());while(num.size()<=9)num.push_back(0);int day=(abs(x-i)+abs(y-j)+1)/2;//回合 int sum=0;//糧食int t=num[0];//當前勞動力 for(int i=1;i<=8;i++)//枚舉人數{int target=i*i*8;//需要多少糧食才能升人口if(sum<target){int temp=(target-sum+t-1)/t;//還需要工作幾個回合 sum+=temp*t;//加上temp回合的貢獻day+=temp;//加上temp回合}t+=num[i];//貪心加上新來的人口}ans=min(ans,day);}printf("%d\n",ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU - 6746 Civilization(贪心+模拟)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。