View difference between Paste ID: 2wFwExkn and 1kFCKxEU
SHOW: | | - or go back to the newest paste.
1
/*
2
testy:
3
2 4 6 14 10 18 16 20 19 24
4
2 4 6 14 10 18 16 20 17 22
5
3 4 6 14 10 18 16 20 17 22
6
7
8
wyniki:
9
25
10
21
11
25
12
13
*/
14
15
16
17
18
#include <iostream>
19
#include <vector>
20
#include <algorithm>
21
22
23
24
using namespace std;
25
26
struct zadanie
27
{
28
	int poczatek;
29
	int koniec;
30
	int dlugosc;
31
};
32
33
34
35
36
bool cmp (zadanie i, zadanie j) 
37
{ 
38
	if(i.poczatek<j.poczatek)
39
		return 1;
40
	else 
41
	{
42
		if(i.poczatek == j.poczatek)
43
			return i.koniec>j.koniec;
44
		else return 0;
45
	}
46
}
47
48
bool cmp2 (zadanie i, zadanie j) 
49
{ 
50
	return(i.dlugosc > j.dlugosc);
51
}
52
53
54
int main()
55
{
56
	vector <zadanie> godziny;
57
	vector <int> pracownicy;
58
	int zadania, ludzie;
59
	cin >> ludzie;
60
	cin >> zadania;
61
62
63
	int roboczogodziny[2];
64
	roboczogodziny [0] = 0;
65
	roboczogodziny [1] = 0;
66
67
68
	godziny.resize(zadania);
69
	pracownicy.resize(ludzie);
70
71
	for(int i=0; i<ludzie; i++)
72
		pracownicy[i] =0;	
73
74
75
		
76
	for (int i=0; i<zadania; i++)
77
	{
78
		cin >>godziny[i].poczatek;
79
		cin >>godziny[i].koniec;
80
		godziny[i].dlugosc = godziny[i].koniec - godziny[i].poczatek;
81
	}
82
	// wczytanie
83
	
84
	// sort do pierwszego typu zadania
85
	unsigned int a;
86
	sort (godziny.begin(), godziny.end(), cmp);
87
	for(unsigned int i=0; i<godziny.size(); i++)
88
	{
89
		a=0;
90
		while(a < pracownicy.size() && pracownicy[a] > godziny[i].poczatek)
91
		a++;
92
		if(a<pracownicy.size())
93
		{
94
			pracownicy[a] = godziny[i].koniec;
95
			//cout << "Pracownik " << a << ": zadanie : " << godziny[i].poczatek << " - " << godziny[i].koniec << endl;
96
			roboczogodziny[0] += godziny[i].dlugosc;
97
		}
98
	}
99
100
	sort (godziny.begin(), godziny.end(), cmp2);
101
102
	for(int i=0; i<ludzie; i++)
103
		pracownicy[i] =0;	
104
105
	for(unsigned int i=0; i<godziny.size(); i++)
106
	{
107
		a=0;
108
		while(a < pracownicy.size() && pracownicy[a] > godziny[i].poczatek)
109
		a++;
110
		if(a<pracownicy.size())
111
		{
112
			pracownicy[a] = godziny[i].koniec;
113
			//cout << "Pracownik " << a << ": zadanie : " << godziny[i].poczatek << " - " << godziny[i].koniec << endl;
114
			roboczogodziny[1] += godziny[i].dlugosc;
115
		}
116
	}
117
118
	if(roboczogodziny[0] < roboczogodziny[1])
119
	{
120
		for(int i=0; i<ludzie; i++)
121
			pracownicy[i] =0;	
122
123
		for(unsigned int i=0; i<godziny.size(); i++)
124
		{
125
			a=0;
126
			while(a < pracownicy.size() && pracownicy[a] > godziny[i].poczatek)
127
			a++;
128
			if(a<pracownicy.size())
129
			{
130
				pracownicy[a] = godziny[i].koniec;
131
				cout << "Pracownik " << a << ": zadanie : " << godziny[i].poczatek << " - " << godziny[i].koniec << endl;
132
				roboczogodziny[1] += godziny[i].dlugosc;
133
			}
134
			
135
		}
136
		cout << "Wypracowane godziny: " << roboczogodziny[1]/2 << endl;
137
	}
138
	else
139
	{
140
		for(int i=0; i<ludzie; i++)
141
			pracownicy[i] =0;
142
		sort (godziny.begin(), godziny.end(), cmp);
143
144
145
146
		for(unsigned int i=0; i<godziny.size(); i++)
147
		{
148
			a=0;
149
			while(a < pracownicy.size() && pracownicy[a] > godziny[i].poczatek)
150
			a++;
151
			if(a<pracownicy.size())
152
			{
153
				pracownicy[a] = godziny[i].koniec;
154
				cout << "Pracownik " << a << ": zadanie : " << godziny[i].poczatek << " - " << godziny[i].koniec << endl;
155
				roboczogodziny[0] += godziny[i].dlugosc;
156
			}
157
		}
158
159
160
161
162
163
164
165
		cout << "Wypracowane godziny: " << roboczogodziny[0]/2 << endl;
166
167
	}
168
169
170
	return 0;
171
}