地域划分

import java.util.Scanner;


public class PartitionLand {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			int n = scanner.nextInt();
			int m = scanner.nextInt();
			int[][] land = new int[m][n];
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					land[i][j] = scanner.nextInt();
				}
			}
			System.out.println(getPartition(land, n, m)[0]);
			System.out.println(getPartition(land, n, m)[1]);
		}
	}

	public static int[] getPartition(int[][] land, int n, int m) {
		int minMisFit = Integer.MAX_VALUE;
		int index = -1; // 用来保存划分位置的临时变量
		int[] result = new int[2];// 返回的结果
		int[] par = new int[n];
		for (int i = 0; i <= n; i++) { // 遍历划分位置
			// 构造划分
			for (int j = 0; j < i; j++) {
				par[j] = 0;
			}
			for (int j = i; j < n; j++) {
				par[j] = 1;
			}
			// 和各个专家的划分进行对比
			int diffNum = 0;
			for (int k = 0; k < m; k++) {
				diffNum += numOfMisFit(par, land[k]);
			}
			if (diffNum < minMisFit) {
				minMisFit = diffNum;
				index = i;
			}
		}
		result[0] = index;
		result[1] = index + 1;
		return result;
	}
	//两个划分的不一致统计
	public static int numOfMisFit(int[] par1, int[] par2) {
		int num = 0;
		for (int i = 0; i < par1.length; i++) {
			if (par1[i] != par2[i]) {
				num++;
			}
		}
		return num;
	}
}

public class Partition {
    public int[] getPartition(int[][] land, int n, int m) {
        // write code here
        int count,bestPos = 0,bestVal = Integer.MAX_VALUE;
        for (int position = -1;position < n;position++){
            count = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j <= position; j++)
                    if (land[i][j]!=0)
                        count++;
                for (int j = position+1; j < n; j++)
                    if (land[i][j]!=1)
                        count++;
            }
            if (count<bestVal){
                bestVal = count;
                bestPos = position+1;
            }
        }
        return new int[]{bestPos,bestPos+1};
    }
}

import java.util.*;

public class Partition {
    public int[] getPartition(int[][] land, int n, int m) {
        // write code here
        
    	if(land==null)
    		return null;
    	int[][] left=new int[m][n+1];
    	int[][] right=new int[m][n+1];
    	for(int i=0;i<m;++i)
    	{
    		left[i][0]=0;
    		right[i][n]=0;
    	}
    	for(int i=0;i<m;++i)
    		for(int j=1,k=n-1;j<=n&&k>=0;++j,--k)
    		{
    			if((land[i][j-1]&1)==1)//说明划分错误
    				left[i][j]=left[i][j-1]+1;
    			else
    				left[i][j]=left[i][j-1];
    			if((land[i][k]&1)==0)//也说明划分错误
    				right[i][k]=right[i][k+1]+1;
    			else
    				right[i][k]=right[i][k+1];
    		}
    	int index=0;
    	int min=Integer.MAX_VALUE;
    	for(int j=0;j<n+1;++j)
    	{
    		int cursum=0;
    		for(int i=0;i<m;++i)
    		{
    			cursum+=left[i][j]+right[i][j];
    		}
    		if(cursum<min)
    		{
    			min=cursum;
    			index=j;
    		}
    	}
    	int[] ans=new int[2];
    	ans[0]=index;
    	ans[1]=index+1;
    	return ans;
    
    }
}
DP，空间换时间，left[i][j]表示第i+1次评估的时候在第j个位置上划分
（包括j，也就是位置j的右边）的得到的错误次数，那么当land[i][j]=1的时候表示
划分错误，left[i][j]=left[i][j-1]，否则，left[i][j]=left[i][j-1],right
原理一样，注意j的取值范围为0~n。
	

//一开始没看懂题意，尴尬==
int min = Integer.MAX_VALUE;
        int position = -1;
        //int count = 0;
        int bestPosition = 0;
        
        for(;position < n;position++){
            int count = 0;
            for(int i = 0;i < m;i++){
                for(int j = 0;j <= position;j++){
                    if(land[i][j] == 1){
                        count++;
                    }
                }
                for(int j = position + 1;j < n;j++){
                    if(land[i][j] == 0){
                        count++;
                    }
                }
            }
            if(min > count){
                min = count;
                bestPosition = position+1;
            }
            
        }
        return new int[]{bestPosition,bestPosition+1};

/**
 * 对@欠扁的小篮子的代码思路进行解释了,但是还是有没看懂的地方,pos为什么要从-1开始而不是从0,
 * 还有为什么bestPos = position + 1;而不是bestPos = position
 */
public class Partition{
	/**
	 * @param land 二维数组
	 * @param n 列数
	 * @param m 行数
	 * @return
	 */
	public int[] getPartition(int[][] land, int n, int m) {
		int count = 0;// 划分到A而专家评估为B的次数和你划分到B而专家评估为A的次数
		int bestPos = 0;// 划分的位置
		int bestVal = Integer.MAX_VALUE;// 次数之和的最小值
		for (int position = -1; position < n; position++) {
			count = 0;
			for (int i = 0; i < m; i++) {//单独对每一行进行判断
				for (int j = 0; j <= position; j++)//0-position种A
					if (land[i][j] != 0)//如果说不是A
						count++;
				for (int j = position + 1; j < n; j++)//position+1-n种B
					if (land[i][j] != 1)
						count++;
			}
			if (count < bestVal) {
				bestVal = count;
				bestPos = position + 1;//因为最开始元素是1
			}
		}
		return new int[] { bestPos, bestPos + 1 };
	}
}

// 观察规律型
// 递推公式
vector<int> getPartition(const vector<vector<int> >& land, int n, int m) {
    vector<int> voteA(n);
    int sumA = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            sumA += 1 - land[j][i];
            voteA[i] += 1 - land[j][i];
        }

    // 不同划分方案
    vector<int> cost(n + 1);
    for (int i = 0; i <= n; ++i)
        if (i == 0) cost[i] = sumA;
        else cost[i] = cost[i - 1] +  m - 2 * voteA[i - 1];
    int max_index = min_element(cost.begin(), cost.end()) - cost.begin();
    vector<int> result;
    result.push_back(max_index);
    result.push_back(max_index + 1);

    return result;
}

# -*- coding:utf-8 -*-

class Partition:
    # land 二维list，每个项为专家给出的划分，例如[[1,1,1,1],[0,0,0,0],[1,0,1,1]]
    # 请函数返回一个划分的list，例如 [0,1]
    def getPartition(self, land, n, m):
        # write code here
        # return [0, 1]
        
        index = 0
        min = 500
        for i in range(n + 1):
            sum = 0
            for j in range(0, m):
                sum += self.compare_block(land[j], i)
            if sum < min:
                index = i
                min = sum
        res = []
        res.append(index)
        res.append(index+1)
        return res

    def compare_block(self, block, sp):
        sum = 0
        ll = len(block)
        for i in range(sp):
            if block[i] == 1:
                sum += 1
        for i in range(sp, ll):
            if block[i] == 0:
                sum += 1
        return sum

class Partition {
public:
    vector<int> getPartition(const vector<vector<int> >& land, int n, int m) {
        // write code here
        vector<int> v;
        int cnt[n+5];
        int min, ind;
        memset(cnt, 0, sizeof cnt);
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(land[i][j]){		//1
                    cnt[j+1]++;
                }
                else{				//0
                	cnt[0]++;
                  	cnt[j+1]--;
                }
            }
        }
        min = cnt[0];	ind = 0;
        for(int i = 1; i <= n; i++){
            cnt[i] += cnt[i-1];
            if(cnt[i] < min){
                min = cnt[i];
                ind = i;
            }
        }
        v.push_back(ind);	v.push_back(ind + 1);
        return v;
    }
};

vector<int> getPartition(const vector<vector<int> >& land, int n, int m) {

    // write code here

    vector<int> errorA(n);

    vector<int> errorB(n);

    for (int i = 0; i < n; i++) {

        int sum = 0;

        for (int j = 0; j< m; j++) {

            sum += land[j][i];

        }

        errorA[i] = sum;

    }

    for (int i = 0; i < n; i++) {

        errorB[i] = m - errorA[i];

    }

    vector<int> errorTime(n+1);

    for (int i = 0; i <= n; i++) {

        int erroa = accumulate(errorA.begin(), errorA.begin()+i, 0);

        int errob = accumulate(errorB.begin()+i, errorB.end(), 0);

        errorTime[i] = erroa+errob;

    }

    int min = errorTime[0];

    int flag = 0;

    for (int i = 1; i<n+1; i++) {

        if(min>errorTime[i])

        {

            min = errorTime[i];

            flag = i;

        }

    }

    vector<int> result;

    result.push_back(flag);

    result.push_back(flag+1);

    return result;

}

	}