电影院选座

#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; 
}

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);
    }
}

js解法：分割1，首尾单独判断

let _str=readline();
_str = _str.replace(/ /g, '');
let _arr = _str.split('1');
_arr = _arr.map((v, i) => {
    if (i === 0 || i === _arr.length - 1) {
        return v.length;
    }
    return Math.ceil(v.length / 2);
})
console.log(Math.max.apply(null, _arr));

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;
        }
    }
}