1.问题描述:

多个编辑对一篇论文进行评审,每个编辑找出若干个病句,用[s, t]表示,s代表病句起始位置,t代表病句终止位置。不同编辑找出的病句可能有重叠,如[1,5]和[2,7],可以合并为[1,7]。要求输入每个编辑找出的病句,输出合并后的所有病句,按病句的起始位置从小到大排序输出。


#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
vector<vector<int>> sentences;		// 病句,将各编辑找出的病句放在一个vector中
 
bool comp(vector<int> &a, vector<int> &b)
{
	return a[1] < b[1];
}
 
void main()
{
	int M;				            // 评审数量
	cin >> M;
 
	// 读取病句
	for (int i = 0; i < M; i++)
	{
		vector<int> sente(3);
		char c;
		do
		{
			sente[0] = 0;			// 辅助标记,0表示未被合并,1表示已被合并
			cin >> sente[1];		// 病句起始位置
			cin.get();				// ","
			cin >> sente[2];		// 病句终止位置
			c = cin.get();			// ";"
			sentences.push_back(sente);
		} while (c == ';');
	}
 
	// 合并病句
	for (int i = 0; i < sentences.size(); i++)
	{
		for (int j = i + 1; j < sentences.size(); j++)
		{
			
			if ((sentences[i][2] >= sentences[j][1] && sentences[i][2] <= sentences[j][2])
				|| (sentences[j][2] >= sentences[i][1] && sentences[j][2] <= sentences[i][2]))	// 需要合并
			{
				sentences[j][1] = sentences[i][1] < sentences[j][1] ? sentences[i][1] : sentences[j][1];	// 新的起始
				sentences[j][2] = sentences[i][2] > sentences[j][2] ? sentences[i][2] : sentences[j][2];	// 新的终止
				sentences[i][0] = 1;		// 标记为已合并
				break;						// 跳到下一个病句
			}
		}
	}
 
	// 排序
	sort(sentences.begin(), sentences.end(), comp);
 
	// 输出
	int flag = 0;				// 标记第一个病句
	for (int i = 0; i < sentences.size(); i++)
	{
		if (!sentences[i][0])
		{
			if (flag)
				cout << ";";
			flag = 1;
			cout << sentences[i][1] << "," << sentences[i][2];
		}
	}
	cin.get();
}



2.题目:

给 n 个正整数 a_1,…,a_n, 将 n 个数顺序排成一列后分割成 m 段,每一段的分数被记为这段内所有数的和,该次分割的分数被记为 m 段分数的最大值。问所有分割方案中分割分数的最小值是多少?

输入描述:
第一行依次给出正整数 n, m。
第二行依次给出n 个正整数 a1,...,an

示例:

输入
5 3
1 4 2 3 5
输出
5
说明
分割成 1 4 | 2 3 | 5 的时候三段的分数都为 5,得到分割分数的最小值。

备注:
对于所有的数据,有 m <= n <= 100000,0 <= ai
<= 2^39。


#include <iostream>
using namespace std;

int Judge(int data[], int sum, int m, int n);
int Binary_Search(int data[], int left, int right, int m, int n);


int main()
{
    int n = 0, m = 0;
    cin >> n >> m;

    int data[n];
    int max_num = 0;
    int sum = 0;

    int i = 0;

    for(i = 0; i < n ; i++)
    {
        cin >> data[i];
        if (data[i] > max_num)
        {
            max_num = data[i];
        }
        sum += data[i];
    }

    cout << Binary_Search(data, max_num, sum, m, n);

    return 0;
}

int Binary_Search(int data[], int left, int right, int m, int n)
{
    int mid = 0;

    while (left < right)
    {
        mid = left + (right - left) / 2;
        if (Judge(data, mid, m, n)) //满足划分,继续向左寻找
        {
            right = mid;//不减是因为无法确保减一之后的数是否满足划分
        }
        else    //不满足划分,继续向右寻找
        {
            left = mid + 1;
        }
    }

    return left;
}

int Judge(int data[], int mid, int m, int n)
{
    int cnt = 0;
    int sum = 0;

    for (int i = 0; i < n; i++)
    {
        if (sum + data[i] > mid) //累加和大于 mid,进行一次划分
        {
            sum = data[i];
            cnt++;
            if (cnt > m - 1)    //划分次数大于 m-1,不满足划分
            {
                return 0;
            }
        }
        else
        {
            sum += data[i];
        }
    }

    return 1;
}

3.给出红、黄、蓝三种颜色的盒子各有若干个(a、b、c),将其排成一排,要求相同颜色的盒子不能相邻,直到盒子用完或者没有合适颜色的盒子为止,输出总共有多少种排列方式?

例如:输入 红:a=1, 黄:b=1,蓝:c=1

输出为:6

例如:输入 红:a=1, 黄:b=2,蓝:c=1

输出为:8


#include<iostream>
#include<Windows.h>
using namespace std;
 
//判断是否有匹配颜色的盒子
bool isNomatch(int a, int b, int c, char r)
{
	switch (r)
	{
	case 'a':
		if (b > 0 || c > 0) return false;
		break;
	case 'b':
		if (a > 0 || c > 0) return false;
		break;
	case 'c':
		if (a > 0 || b > 0) return false;
		break;
	}
	return true;
}
 
//在第一个确定为红、黄、蓝盒子的情况下统计排列种类
void arrage(int a, int b, int c, char r, int &sortCount)
{
	if (a + b + c == 0 || isNomatch(a, b, c, r))
	{
		sortCount++;
		return;
	}
	if (a > 0 && r != 'a')
	{
		a--;
		arrage(a, b, c, 'a', sortCount);
		a++;
	}
	if (b > 0 && r != 'b')
	{
		b--;
		arrage(a, b, c, 'b', sortCount);
		b++;
	}
	if (c > 0 && r != 'c')
	{  
		c--;
		arrage(a, b, c, 'c', sortCount);
		c++;
	}
}
 
//分别对第一个盒子为红、黄、蓝盒子的情况进程遍历累加其总共的排列数
int calculateCount(int a, int b, int c)
{
	int count = 0;
	char r;
	int t[3] = { a,b,c };
	for (int i = 0, r = 'a'; i < 3; i++, r++)
	{
		t[i]--;
		arrage(t[0], t[1], t[2], r, count);
		t[i]++;
	}
	return count;
}
 
//运行代码
int main()
{
	cout << calculateCount(1,2,1) << endl;
	system("pause");
	return 0;
}