疫情逐步缓和后,电影院终于开业了,但是由于当前仍处于疫情期间,应尽量保持人群不聚集的原则。
所以当小易来电影院选定一排后,尽量需要选择一个远离人群的位置。
已知由0和1组成的数组表示当前排的座位情况,其中1表示已被选座,0表示空座
请问小易所选座位和最近人的距离座位数最大是多少?
有如下假设:至少有一个人已选座,至少有一个空座位,且座位数限制为
一行由0和1组成的整数数组
仅一行一个整数表示答案
1 0 0 0 1 0 1
2
小易第3个座位最合适,则和座位1/座位5的距离为2
1 0 1 0 1
1
小易可以选择第2个座位或者第4个座位,距离为1
import java.io.*; import java.util.*; import java.util.concurrent.atomic.AtomicInteger; public class Main { public static void main(String[] args) throws IOException { Scanner scanner = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out); char[] line = scanner.nextLine().toCharArray(); int n = line.length; boolean [] seats = new boolean[n/2+1]; for (int i = 0; i < n; i+=2) { seats[i/2] = (line[i] == '1'); } n = seats.length; int disFinal = 0; for (int i = 0; i < n; i++) { if(!seats[i]) { int l = i-1; while (l>=0 && !seats[l]){ --l; } int dis = (l >= 0 ? i-l : Integer.MAX_VALUE); int r = i+1; while (r<n && !seats[r]){ ++r; } if(r<n && dis > r-i) { dis = r - i; } if(dis > disFinal){ disFinal = dis; } } } out.println(disFinal); out.flush(); } }
#include <bits/stdc++.h> using namespace std; class Hungary{ public: Hungary(unordered_map<int, vector<int>> &g, int n){ this->g = g; match.resize(n, -1); N = n; } //寻找增广路径 bool findAugment(int i){ for(auto &neig: g[i]){ if(vis.count(neig)) continue; vis.insert(neig); if(match[neig] == -1|| findAugment(match[neig])){ match[i] = neig; match[neig] = i; return true; } } return false; } //寻找最小覆盖,或者最大匹配 int minCover(){ int ret = 0; for(int i = 0;i < N; i++){ if(match[i] == -1){ vis.clear(); if(findAugment(i)){ ret ++; } //打印匹配情况 } } return ret; // return (ret == INT_MAX)?-1: ret; } private: unordered_map<int, vector<int>> g; vector<int> match; //记录每个项目由谁担任负责人 unordered_set<int> vis;//项目 int N;//顶点数量 }; int main(){ ios::sync_with_stdio(false); // ifstream cin("data.txt"); // if(!cin.is_open()){ // cerr<<"cannot open data.txt"<<endl; // exit(-1); // } cin.tie(0); string line; getline(cin, line); stringstream ss(line); string tmp; //按照空格进行切分 unordered_map<int,int> A; int ind = 0; while(ss >> tmp){ A[stoi(tmp)] = ind++; } getline(cin, line); stringstream ss1(line); while(ss1 >> tmp){ A[stoi(tmp)] = ind++; } int N; cin>>N; //把匹配的A,B员工当作一条边,然后构建图,要求 unordered_map<int, vector<int>> g; int tA,tB; for(int i = 0;i < N;i++){ cin>>tA>>tB; g[A[tA]].emplace_back(A[tB]); g[A[tB]].emplace_back(A[tA]); } //思路:一个负责人应该负责尽可能多的项目 //每次寻找最大度的节点并减去相应的边,直到所有边都有人负责 Hungary h(g, A.size()); printf("%d\n", h.minCover()); return 0; }C++版本供参考
public class Main { public static int method(Integer[] arr,int start,boolean[] visit){ if(start<0||start>arr.length-1||visit[start]) return 2000; if (arr[start]==1) return 0; visit[start] = true; int left=method(arr,start-1,visit)+1; int right=method(arr,start+1,visit)+1; return Math.min(left, right); } public static void main(String[] args) { List<Integer> list = new ArrayList<>(); Scanner sc = new Scanner(System.in); while (sc.hasNextInt()) { list.add(sc.nextInt()); } Integer[] arr = list.toArray(new Integer[list.size()]); int res=0; for (int i = 0; i < arr.length; i++) { res = Math.max(res, method(arr, i, new boolean[arr.length])); } System.out.println(res); } }
seats = list(map(int, input().strip().split())) n = len(seats) # 先找到左边第一个1出现的索引 edge = seats.index(1) l_bound = edge r_bound = n - 1 # 再找右边第一个1出现的索引,两者选大的作为边缘最大的距离 for i in range(n - 1, -1, -1): if seats[i] == 1: edge = max(edge, n - 1 - i) right = i break # 对于从left~right的子数组,寻找其中两个相邻1最大的距离即可 distance = 0 ones_idx = [l_bound] for i in range(l_bound + 1, r_bound + 1): if seats[i] == 1: distance = max(distance, i - ones_idx[-1]) ones_idx.append(i) print(max(edge, distance // 2))
java,时间O(n)的解法,双指针实现import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); String[] s1 = scan.nextLine().split(" "); scan.close(); int[] nums = new int[s1.length]; for (int i = 0; i < nums.length; i++) nums[i] = Integer.parseInt(s1[i]); int res = 0; int left, right; for (int i = 0; i < nums.length; i++) { if (nums[i] == 1) continue; left = i-1; right = i+1; int tmpRes = 1; while (left >= 0 || right < nums.length) { if ((left >= 0 && nums[left] == 1) || (right < nums.length && nums[right] == 1)) { res = Math.max(res, tmpRes); break; } if (left >= 0) left--; if (right < nums.length) right++; tmpRes++; } if (left < 0 && right >= nums.length) res = Math.max(res, tmpRes); } System.out.println(res); } }
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); //01组成的字符串 String[] strArr = scanner.nextLine().split(" "); StringBuilder sb = new StringBuilder(); for (int i = 0; i < strArr.length; ++i){ sb.append(strArr[i]); } String str = sb.toString(); int num = find(str); System.out.println(num); } private static int find(String str) { //分情况讨论: //1.最左边是0,那么可以确定一个临时的较大值。左边到第一个1出现的位置。 //2.最右边是0,确定另外一个较大值。最右边到往前第一个1出现的位置。 //3.最后一个最大值。左边第一个1和右边第一个1中间连续0的一半。 int len = str.length() - 1; //1.第一个1出现的位置(从左边开始算) int left = str.indexOf('1'); //2.最后一个1出现的位置 int right = str.lastIndexOf('1'); //边界位置的较大值 int max = Math.max(left, len - right); //找到中间位置的最大值 int tempMax = 0; //保存临死的最大值 while(left < right){ //找到下个0出现位置 int tempLeft = str.substring(left, right+1).indexOf('0') + left; //下个1出现的位置 int tempRight = str.substring(left + 1, right + 1).indexOf('1') + left + 1; //没有0了,直接跳出 if (tempLeft < left){ break; } //进行计算 tempMax = Math.max(tempMax, tempRight - tempLeft); //更新左边的边界 left = tempRight; } tempMax = (tempMax % 2) == 0 ? tempMax : tempMax + 1; return Math.max(max, tempMax / 2); } }
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); String[] siteMap=sc.nextLine().split(" "); int[] site=new int[siteMap.length]; for (int i = 0; i < siteMap.length; i++) { site[i]=Integer.parseInt(siteMap[i]); } System.out.println(maxGap(site)); } private static int maxGap(int[] site) { int n=site.length; //dp数组存放离得最近的人的距离 int[] dp=new int[n]; int max=0; for (int i = 0; i < n; i++) { if(site[i]==1) continue; //座位没有人的情况 if(i>0&&dp[i-1]==0) dp[i]=1; else if((i<n-1&&site[i+1]==1)||i==n-1){ dp[i]=1; max=Math.max(max,dp[i]); }else { int j=i+1; while (j<n&&site[j]==0){j++;} dp[i]= i==0?j:Math.min(dp[i-1]+1,j-i); max=Math.max(max,dp[i]); if(j!=n){ for (int k = i+1; k < j; k++) { dp[k]=Math.min(dp[k-1]+1,j-k); max=Math.max(max,dp[k]); } //注意右边界 1 1 1 0 0 0 这种情况 座位只有左边有人 }else { for (int k = i+1; k < j; k++) { dp[k]=dp[k-1]+1; max=Math.max(max,dp[k]); } } i=j; } } return max; } }
import java.util.Scanner; public class Main { public static int movie(int[] nums) { int left = -1; int right = 0; int max = 0; while (right < nums.length) { while (right < nums.length && nums[right] == 0) { right++; } if (left == -1) max = Math.max(max, right); else { if (right == nums.length) max = Math.max(max, right - left); else max = Math.max(max, (right - left) % 2 == 1 ? (right - left) / 2 + 1 : (right - left) / 2); } left = right + 1; right++; } return max; } public static void main(String[] args) { Scanner s = new Scanner(System.in); String s1 = s.nextLine(); String[] s2 = s1.split(" "); int[] arr = new int[s2.length]; int k = 0; for (String str : s2) { arr[k++] = Integer.parseInt(str); } int movie = movie(arr); System.out.println(movie); s.close(); } }
package main import( "fmt" "bufio" "os" "strings" "strconv" ) func main(){ lastOne,finding, maxDist := -1,false, 0 reader := bufio.NewReader(os.Stdin) line, _ := reader.ReadString('\n') line_str := strings.Split(line[0:len(line)-1]," ") for i, s := range(line_str){ arg, _ := strconv.Atoi(s) if arg==1 { finding = false if lastOne == -1 { maxDist = i } else{ dist := (i - lastOne) >> 1 if dist > maxDist { maxDist = dist } } lastOne = i } else { finding = true } } if finding { dist := len(line_str) - lastOne - 1 if dist > maxDist { maxDist = dist } } fmt.Println(maxDist) }
nums=list(map(int,input().strip().split())) n=len(nums) left=[0 for _ in range(n)] right=[0 for _ in range(n)] cnt1,cnt2=0,0 if nums[0]==0: i=1 cnt1+=1 while nums[i]==0: cnt1+=1 i+=1 if nums[-1]==0: i=n-2 cnt2+=1 while nums[i]==0: cnt2+=1 i-=1 for i,num in enumerate(nums): if num==1: left[i]=0 else: if i==0: left[i]=1 else: left[i]=left[i-1]+1 for i in range(len(nums)-1,-1,-1): if nums[i]==1: right[i]=0 else: if i<n-1: right[i]=right[i+1]+1 else: right[i]=1 ret=0 for i in range(len(nums)): ret=max(ret,min(left[i],right[i])) ret=max(ret,cnt1,cnt2) print(ret)
#include<bits/stdc++.h> using namespace std; int a[1001]; int main(){ int index=0; vector<int> v; while(cin>>a[index++]){ if(cin.get()=='\n'){ break; } } for(int i=0;i<index;i++){ if(a[i]==1){ v.push_back(i); } } int res = 0; for(int i=1;i<v.size();i++){ res = max(res,(v[i]-v[i-1])/2); } if(v[0]!=0) res = max(res,v[0]-0); if(v[v.size()-1]!=index-1) res = max(res,index-1-v[v.size()-1]); cout<<res; return 0; }
public static void main(String[] args) { Scanner scan = new Scanner(System.in); String s = scan.nextLine(); int i = s.indexOf('1'); if (i == -1) { System.out.println((s.length()+1)/2); return; } int j = i; int len = i; while (i < s.length()) { while (i < s.length() && s.charAt(i) == '1') i++; j = i; while (j < s.length() && s.charAt(j) == '0') j++; len = Math.max(len, j-i); i = j; } System.out.println((len+1)/2); }为啥超时了呢?我觉得这样复杂度并不大吧?
#include <cstdio> #include <iostream> #include <string> #include <string.h> #include <vector> using namespace std; int a[1001]; int b[1001]; int main(){ int index=0; int maxx=0; vector<int> v; vector<int> m; while(cin>>a[index++]){ if(cin.get()=='\n'){ break; } } for(int i=0;i<index;i++){ if(a[i]==1){ v.push_back(i); } } if(v.size()==1){ if(v[0]<(index-v[0]-1)){ cout<<(index-v[0]-1); }else{ cout<<v[0]; } return 0; } for(int i=0;i<v.size()-1;i++){ m.push_back(v[i+1]-v[i]-1); } for(int i=0;i<m.size();i++){ if(maxx<m[i]){ maxx=m[i]; } } if(v[0]>maxx){ maxx=v[0]; } if(maxx%2==0){ if(maxx/2<(index-1-v[v.size()-1])){ cout<<index-1-v[v.size()-1]; }else if(maxx/2<v[0]){ cout<<v[0]; }else{ cout<<maxx/2; } } if(maxx%2!=0){ if(maxx/2+1<(index-1-v[v.size()-1])){ cout<<index-1-v[v.size()-1]; }else if(maxx/2+1<v[0]){ cout<<v[0]; }else{ cout<<maxx/2+1; } } return 0; }
public class Seat { public static void main(String[] args) { String s = "100100000000110001"; int seat = findSeat(s); System.out.println(seat); } public static int findSeat(String a){ int start; int end; //找到首末1出现的坐标 start = a.indexOf('1'); end = a.lastIndexOf('1'); //截取字符串 String temp = a.substring(start, end+1); int division = 0;//间隔 int count = 0;//连续出现的0的个数 for (int i = 1; i < temp.length()-1; i++) { if (temp.charAt(i) == '0'){ count++; }else { if (count > (division*2)){ division = count / 2; } count = 0; } } //判断首末空余的位置与中间可选位置间隔大小 if (start > division && (a.length() - 1 - end) > division){ if (start > (a.length() - 1 - end)){ return start; }else { return a.length() - 1 - end; } }else { return division; } } }