題目鏈接：點(diǎn)擊查看

題目大意：現(xiàn)在固定人初始時(shí)在點(diǎn)0處，現(xiàn)在我們需要跨過(guò)長(zhǎng)度為n的一條河，到達(dá)對(duì)岸的點(diǎn)n+1處，給出m個(gè)木板，我們可以將這m個(gè)木板隨意擺放，但相對(duì)位置不能改變，并且只能互相接觸而不能互相重疊，現(xiàn)在人每次可以跳d個(gè)單位，問(wèn)是否能夠利用給出的m個(gè)木板到達(dá)河對(duì)岸，若能的話給出任意一種構(gòu)造方案

題目分析：首先這個(gè)題目肯定是要貪心做的了，因?yàn)樾枰獦?gòu)造方案，所以我們還需要注意一個(gè)小細(xì)節(jié)，那就是全部木板都要使用，那么我們一開(kāi)始可以維護(hù)一個(gè)sum和，維護(hù)一下所有木板的總長(zhǎng)度，如果所有木板的總長(zhǎng)度加上所有木板的間隔和人可以跳躍的乘積仍然小于河的長(zhǎng)度，那必然是無(wú)法構(gòu)造的了，其他情況都是有解的了

如果有解的話，我們直接貪心找就好了，假設(shè)我們的當(dāng)前位置為pos，當(dāng)前剩余木板的長(zhǎng)度為sum，那么每次我們假設(shè)都先跳一次，然后再加上木板的長(zhǎng)度，也就是判斷一下這一次需不需要跳，只需要判斷一下pos+sum+d-1是否能夠直接到達(dá)n+1的位置，若能的話就先跳一次，然后其余的木板直接連成一個(gè)長(zhǎng)木板拼在后面即可，若不能的話我們就先跳一步，然后拼上相應(yīng)的木板，如此往復(fù)構(gòu)造答案即可

這個(gè)題目最煩人的就是木板的長(zhǎng)度中有些運(yùn)算需要自己動(dòng)手畫(huà)畫(huà)圖，看看具體的關(guān)系，因?yàn)橛械年P(guān)系是需要減一的，大概就是這樣了，簡(jiǎn)單貪心

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e3+100;int a[N];int ans[N];int main() { // freopen("input.txt","r",stdin);int n,m,d;scanf("%d%d%d",&n,&m,&d);int sum=0;for(int i=1;i<=m;i++){scanf("%d",a+i);sum+=a[i];}if(sum+(m+1)*(d-1)<n)//特判一下NO的情況return 0*printf("NO\n");printf("YES\n");int pos=0;//當(dāng)前位置 for(int i=1;i<=m;i++){if(pos+sum+d-1<n+1)//如果不能直接跳到對(duì)岸pos+=d;else//如果可以直接跳到對(duì)岸，用剩下的木板拼成一整個(gè)長(zhǎng)木板pos=n+1-sum;for(int j=pos;j<=pos+a[i]-1;j++)//構(gòu)造答案ans[j]=i;pos+=a[i]-1;//實(shí)時(shí)更新當(dāng)前位置sum-=a[i];//實(shí)時(shí)更新剩余木板的長(zhǎng)度}for(int i=1;i<=n;i++)printf("%d ",ans[i]);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1256C Platforms Jumping(贪心+构造)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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