Untitled

mail@pastecode.io avatar
unknown
plain_text
7 days ago
2.0 kB
2
Indexable
Never
#include<iostream>
#include<queue>
#include<unordered_map>

using namespace std;

struct connect
{
	int id;
	int length;
	int ori;
	int sl;
};

int city[100];
int path[100];
int N;
int min_max, max_max;

struct compare
{
	bool operator()(connect a,connect b)
	{
		if (a.length == b.length)
			return a.id > b.id;
		return a.length < b.length;
	}
};

priority_queue<connect, vector<connect>, compare> path_queue;

int add(int M)
{
	connect tmp;
	int res = 0;
	while (M--)
	{
		tmp = path_queue.top();
		path_queue.pop();
		//
		tmp.sl++;
		tmp.length = tmp.ori / tmp.sl;
		path[tmp.id] = tmp.length;
		res = tmp.length;
		//
		path_queue.push(tmp);
	}
	return res;
}

int distan(int a, int b)
{
	int res = 0;
	for (int i = a; i < b; i++) res += path[i];
	return res;
}

bool kiemtra(int sum,int sl,int start,int endd)
{
	int tmp = 0;
	int cnt = 0;
	for (int i = start; i <= endd; i++)
	{
		if (city[i] > sum) return false;

		tmp += city[i];
		if (tmp > sum)
		{
			cnt++;
			tmp = city[i];
		}
	}
	cnt++;
	if (cnt <= sl) return true;
	return false;
}

int group(int a, int b, int g)
{
	int top = max_max;
	int bot = min_max;
	int res = 0;
	while (top >= bot)
	{
		int mid = (top + bot) / 2;
		bool check = kiemtra(mid,g,a,b);
		if (check)
		{
			res = mid;
			top = mid - 1;
		}
		else
		{
			bot = mid + 1;
		}
	}
	return res;
}

int main()
{
	//
	FILE* input;
	freopen_s(&input, "input.txt", "r", stdin);
	cin >> N;
	min_max = 0;
	max_max = 0;
	for (int i = 0; i < N; i++)
	{
		cin >> city[i];
		max_max += city[i];
		if (city[i] > min_max) min_max = city[i];
		if (i > 0)
		{
			path[i - 1] = city[i - 1] + city[i];
			connect newconnect = {i-1,path[i-1],path[i-1],1};
			path_queue.push(newconnect);
		}
	}
	//
	int res1 = add(1);
	int res2 = add(2);
	int res3 = distan(0, 5);
	int res4 = distan(1, 2);
	int res5 = group(0, 5, 3);
	int res6 = group(1, 4, 2);
	//
	return 0;
}
Leave a Comment