1.均分紙牌

題目描述

有 NNN 堆紙牌，編號(hào)分別為 1,2,…,N1,2,…,N1,2,…,N 。每堆上有若干張，但紙牌總數(shù)必為 NNN 的倍數(shù)。可以在任一堆上取若干張紙牌，然后移動(dòng)。

移牌規(guī)則為：在編號(hào)為 111 堆上取的紙牌，只能移到編號(hào)為 222 的堆上；在編號(hào)為 NNN 的堆上取的紙牌，只能移到編號(hào)為 N?1N-1N?1 的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊的堆上。

現(xiàn)在要求找出一種移動(dòng)方法，用最少的移動(dòng)次數(shù)使每堆上紙牌數(shù)都一樣多。

例如 N=4N=4N=4 ， 444 堆紙牌數(shù)分別為：

① 999 ② 888 ③ 171717 ④ 666

移動(dòng) 333 次可達(dá)到目的：

從 ③ 取 444 張牌放到 ④ （ 9,8,13,109,8,13,109,8,13,10 ）-> 從 ③ 取 333 張牌放到 ②（ 9,11,10,109,11,10,109,11,10,10 ）-> 從 ② 取 111 張牌放到①（ 10,10,10,1010,10,10,1010,10,10,10 ）。

輸入輸出格式

輸入格式：

兩行

第一行為： NNN （ NNN 堆紙牌， 1≤N≤1001 \le N \le 1001≤N≤100 ）

第二行為： A1,A2,…,AnA_1,A_2, … ,A_nA1?,A2?,…,An? （ NNN 堆紙牌，每堆紙牌初始數(shù)， l≤Ai≤10000l \le A_i \le 10000l≤Ai?≤10000 ）

輸出格式：
一行：即所有堆均達(dá)到相等時(shí)的最少移動(dòng)次數(shù)。

?

?

特別好理解的。是一個(gè)很典型的貪心算法。這個(gè)題應(yīng)該想到用每個(gè)數(shù)都減去平均張數(shù)，題目就變成了要移動(dòng)的數(shù)量。正數(shù)表示要移走，負(fù)數(shù)表示要移過來。如果本來就有0張?jiān)趺崔k呢？那么就要有過濾這個(gè)步驟了。

while(a[i]==0&&i<n)i++;//過濾掉左邊的0 while(a[j]==0&&j>1)j--;//過濾掉右邊的

當(dāng)然在移牌過程中也不能忘記過濾每個(gè)過程中產(chǎn)生的0牌。

while(a[i]==0&&i<j) i++;

那么代碼如下

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int ave,n,a[110]; int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];ave+=a[i];}ave=ave/n;for(int i=1;i<=n;i++) a[i]-=ave;int i=1,j=n;int step;while(a[i]==0&&i<n)i++;while(a[j]==0&&j>1)j--;while(i<j){a[i+1]+=a[i];a[i]=0;step++,i++;while(a[i]==0&&i<j) i++;}cout<<step; }

用for循環(huán)寫的版本如下

#include<iostream> using namespace std; int n,w,i,j,a[10010],step; int main(){cin>>n;for(i=1;i<=n;i++){cin>>a[i];w+=a[i];}w/=n;for(i=1;i<=n;i++) a[i]-=w;i=1;j=n;for(i=1;i<=n;i++){if(a[i]!=0){a[i+1]+=a[i];a[i]=0;step++;}}cout<<step; }

?

?

?

2.迷宮和走迷宮（我也不知道這是一個(gè)什么順序了做著玩吧）

?

迷宮就直接貼代碼就好了，反正就是裸的dfs

#include<iostream> #include<cstdio> using namespace std; int n,m,t,sx,sy,fx,fy,sum=0; int flag[101][101],trap1,trap2; void search(int i,int j){if(i==fx&&j==fy){sum++;return;}else {flag[i][j]=1;if((j!=m)&&(flag[i][j+1]==0)) search(i,j+1),flag[i][j+1]=0;//you if((i!=n)&&(flag[i+1][j]==0)) search(i+1,j),flag[i+1][j]=0;//xiaif((i!=1)&&(flag[i-1][j]==0)) search(i-1,j),flag[i-1][j]=0;//shangif((j!=1)&&(flag[i][j-1]==0)) search(i,j-1),flag[i][j-1]=0;//zuo } } int main(){cin>>n>>m>>t;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){flag[i][j]=0;}cin>>sx>>sy>>fx>>fy;for(int i=1;i<=t;i++){cin>>trap1>>trap2;flag[trap1][trap2]=1;}search(sx,sy);cout<<sum; }

走迷宮就比迷宮多一個(gè)輸出路徑的操作

注意優(yōu)先級(jí)：左上右下

設(shè)置一個(gè)bool變量pd來判斷有沒有路徑。用一個(gè)step來記錄步數(shù)。

#include<iostream> #include<cstdio> #include<cmath> using namespace std; int m,n,a[16][16]; int a1[1001],b1[1001]; int bix,biy,enx,eny; bool pd;void read(){cin>>m>>n;for(int i=1;i<=m;i++)for(int j=1;j<=n;j++){cin>>a[i][j];}cin>>bix>>biy;cin>>enx>>eny; }void print(int p){pd=1;for(int i=0;i<p;i++){cout<<"("<<a1[i]<<","<<b1[i]<<")->";}cout<<"("<<enx<<","<<eny<<")";cout<<endl; }void search(int x,int y,int step){if (x < 1 || y < 1 || x>m || y>n) return;if(x==enx&&y==eny){print(step);return;}if(a[x][y]==1){a1[step]=x;b1[step]=y;a[x][y]=0;search(x,y-1,step+1);search(x-1,y,step+1);search(x,y+1,step+1);search(x+1,y,step+1);a[x][y]=1;} }int main(){read();search(bix,biy,0);if(pd==0) cout<<"-1"; }

?

?

3.跳石頭

題目背景

一年一度的“跳石頭”比賽又要開始了!

題目描述

這項(xiàng)比賽將在一條筆直的河道中進(jìn)行，河道中分布著一些巨大巖石。組委會(huì)已經(jīng)選擇好了兩塊巖石作為比賽起點(diǎn)和終點(diǎn)。在起點(diǎn)和終點(diǎn)之間，有 NNN 塊巖石（不含起點(diǎn)和終點(diǎn)的巖石）。在比賽過程中，選手們將從起點(diǎn)出發(fā)，每一步跳向相鄰的巖石，直至到達(dá)終點(diǎn)。

為了提高比賽難度，組委會(huì)計(jì)劃移走一些巖石，使得選手們?cè)诒荣愡^程中的最短跳躍距離盡可能長。由于預(yù)算限制，組委會(huì)至多從起點(diǎn)和終點(diǎn)之間移走 MMM 塊巖石（不能移走起點(diǎn)和終點(diǎn)的巖石）。

輸入輸出格式

輸入格式：

第一行包含三個(gè)整數(shù) L,N,ML,N,ML,N,M ，分別表示起點(diǎn)到終點(diǎn)的距離，起點(diǎn)和終點(diǎn)之間的巖石數(shù)，以及組委會(huì)至多移走的巖石數(shù)。保證 L≥1L \geq 1L≥1 且 N≥M≥0N \geq M \geq 0N≥M≥0 。

接下來 NNN 行，每行一個(gè)整數(shù)，第 iii 行的整數(shù) Di(0<Di<L)D_i( 0 < D_i < L)Di?(0<Di?<L) ， 表示第 iii 塊巖石與起點(diǎn)的距離。這些巖石按與起點(diǎn)距離從小到大的順序給出，且不會(huì)有兩個(gè)巖石出現(xiàn)在同一個(gè)位置。

輸出格式：

一個(gè)整數(shù)，即最短跳躍距離的最大值。

?

典型的二分題。二分查找，需要寫一個(gè)judge函數(shù)，來判斷移走的個(gè)數(shù)。若是移走的個(gè)數(shù)符合要求，記錄下來，再搜索其他的是否符合要求，輸出最合適的值。

?

// luogu-judger-enable-o2 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int l,n,m,a[1000010],i,sum=0,mid; int s,e;bool judge(int x){int time=0;int i=0;int now=0;while(i<n+1){i++;if(a[i]-a[now]<x){time++;}else now=i;}if(time>m) return false;else return true;} int main(){cin>>l>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];a[n+1]=l;s=1;e=l;while(s<=e){mid=(s+e)/2;if(judge(mid)){sum=mid;s=mid+1;}else e=mid-1;}cout<<sum<<endl; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/civilization-ga/p/9334477.html

總結(jié)

以上是生活随笔為你收集整理的【清北前紧急补课3】水题集锦的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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