字节跳动ZJ6->编程题二
编程题2
http://www.nowcoder.com/questionTerminal/43068a1013b4417a85c2c2ce8b18159e
1. 思路
- 首先得明白题目意思,就是拿一个房间拿出来往后顺时针分配。【2333评论区里有人说题目描述和xyi】
所以分完最少的肯定就是被分配的,但是有些房间原本没人那就有可能多个最少的,怎么办呢?这种情况离分完 顺时针序最近的那个就是了,所以 分情况讨论即可
2. 初级代码【老太婆的裹脚布。。。而且才过了两个样例的暴力法,后面过不了了,调试应该能调试好,不过练习情况没必要浪费时间知道思路就好了】
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int main(){ int n=0,m=0; long long people=0; cin>>n>>m; long long a[n];//这个房间承受了他本不该承受的重量 memset(a,0,sizeof(a)); for(int i=0;i<n;i++) cin>>a[i]; int min=9999,dex=-2; for(int i=0;i<n;i++) { if(a[i]<min) { min=a[i]; dex=i; } } if(dex<m-1)//说明当前找到的就是ok的 最近 { //dex为分配房间 dex值为几轮 for(int i=0;i<n;i++) { if(i<dex) cout<<a[i]-a[dex]<<" "; else if(i==dex) cout<<a[dex]+m-dex; else { if(i<m) cout<<a[i]-a[dex]-1<<" "; else cout<<a[i]-a[dex]<<" "; } } } else if(dex>m-1)//那就找0到m有没有这个最近的 { for(int i=m;i>0;i--){ if(a[i]==a[dex]) { dex=i; break; } } for(int i=0;i<n;i++) { if(i<m) cout<<a[i]-a[dex]-1<<" "; else if(i==dex) cout<<a[dex]+n-1-m+dex; else { cout<<a[i]-a[dex]<<" "; } } } else{ for(int i=0;i<n;i++) { if(i<dex) cout<<a[i]-a[dex]<<" "; else if(i==dex) cout<<a[dex]+m-dex+1; else { if(i<m) cout<<a[i]-a[dex]-1<<" "; else cout<<a[i]-a[dex]<<" "; } } } //cout<<"people"<<people<<a[dex]<<"m"<<m<<"dex"<<dex<<endl; cout<<endl; return 0; }
3.观摩大佬nbgao
- 首先思路是一样的 不过他刚开始没有记录最小的房间号下标。但他的逆时针倒转思想非常好。
- 关于最小值初始化,他用得是LONG_MAX;这个就很好了 比我以前的9999更安全,这道题里面9999就炸了。INT_MAX也是同理。
#include <bits/stdc++.h> using namespace std; int main(){ int n, x; cin>>n>>x;//n是房间数 x是最后一个的分配位 long a[n], s=0, Min=LONG_MAX; for(int i=0;i<n;i++){ cin>>a[i]; if(a[i] < Min) Min = a[i];//第一趟遍历获取最小值 } int k = x-1;//假设最后分配的那是最小的【-1是因为数组下标为0】 while(a[k] != Min)//如果这个不是最小 k = (k+n-1)%n;//那就左移动 因为原本是顺时针 现在逆时针回去找 for(int i=0;i<n;i++) a[i] -= Min;//所有数都减去遍历的趟数 for(int i=x-1;i!=k;){//i从最后分配的那个 向前-1找为形成整趟的 且i!=k a[i]--;//k右边再-1 s++;//找出未成趟的总数 i = (i+n-1)%n; } a[k] += s + n*Min;//目标最小 加上趟数*总数+未成趟的总量就是正确的 for(int i=0;i<n;i++) cout<<a[i]<<" ";//按序输出 return 0; }