• 1. pháp tham lam để giải quyết bài toán lập lịch công việc. SVTH: Nguyễn Danh Thanh
• 2. biểu bài toán 2 Giải quyết bài toán 3 Chứng minh tính đúng đắn 4 Tính toán độ phức tạp 5 Giới thiệu chương trình 6 Ứng dụng thực tế
• 3. bài toán 1.1 Bài toán Cho n việc cần phải hoàn thành, mỗi việc thực hiện trong 1 đơn vị thời gian. Việc i sẽ đem lại wi tiền thưởng nếu hoàn thành đúng hạn di . [?].Tìm cách thực hiện các công việc để có lợi nhuận cao nhất mà thời gian thực hiện là ít nhất.
• 4. bài toán 1.2 Ví dụ Làm việc nào trước đây !!!!......
• 5. bài toán 1.3 Input/Output Input: n bộ {i , di , wi } i = 1…n; di € N+ ; wi € Z+. Output: B, T. i: Công việc thứ i. di: Thời điểm kết thúc công việc i. wi: Số tiền được thưởng nếu hoàn thành công việc i. B: Lịch thực hiện công việc sao cho T là lớn nhất. T: Tổng số tiền được thưởng.
• 6. bài toán 2.1 Ý tưởng 30s Bước 1: Xác định tất cả các lịch có thể tạo ra từ n công việc. Bước 2: Tính tổng số phần thưởng ở mỗi lịch. Bước 3: So sánh tổng phần thưởng ở các lịch -> Đưa ra lịch cần tìm và tổng tiền thưởng tương ứng.
• 7. bài toán 2.2 Ý tưởng 30s Xếp n công việc vào n thời điểm ta có n! cách -> có n! lịch. Với n = 3 -> 3! = 6 n = 10 -> 10! = 3 628 800 n = 60 -> 60! = 8.32 x 1081 …………………………… n = 10000 ? Có cách khác không ?
• 8. bài toán 2.3 Sử dụng phương pháp tham lam - Sắp xếp lại lịch theo chiều không tăng của phần thưởng wi. Thay đổi i và di tương ứng. - Xét trục thời gian B[m]. m = max(di), k=0. + Nếu giờ b[di] trên B rỗi thì gán b[di] = i. + Nếu giờ b[di] trên B đã bận thì tìm giờ b[j] (j< di) rỗi gần b(di) nhất. Nếu tồn tại giờ b[j] thì gán b[j] = i. Ngược lại c[k++]= i. - Dồn các việc i trên B để tạo lịch làm việc trù mật. - Bổ xung các việc trên C vào B.
• 9. bài toán 2.3 Sử dụng phương pháp tham lam ! Thời gian(h) 1 2 3 4 5 6 7 8 9 Công việc Tiền thưởng ($) Công việc (i) Thời hạn (di) Tiền thưởng (wi) 5 3 90 6 7 60 3 4 50 4 6 40 2 2 40 8 2 30 1 4 20 7 9 10 1 4 20 2 5 3 4 6 7 30 40 90 50 40 60 10 8 1 20 Tổng tiền thưởng : T = 320!
• 10. bài toán 2.4 Giải thuật: 1. Sort W, wi > =wj . vs j > i. and change ai ,di 2. T = 0; m = max(di); B[i] = 0, i = 0…m, k = 0. For i = 1 to n do j = di while B[j] > 0 do - - j. if j = 0 then C[k++] = ai . else B[j] = ai . T += wi . Exit for 3. f0 = 0, For i = 1 to m do if B[i] > 0 then B[f0++] = B[i]. 4. B = B +C. Return B, T.
• 11. tính đúng đắn 1.Thời gian thực hiện n công việc là ít nhất. Lịch làm việc trù mật. Thời điểm bj thực hiện chỉ công việc i. N công việc. => Thời gian thực hiện là n đvtg. 2.Phần thưởng nhận được là lớn nhất. Xét {ci}. i =1…n ci > cj . Tại mỗi bước chọn pi, wi đạt max. Tổng phần thưởng nhận được là lớn nhất
• 12. tạp thuật toán 4.1 Độ phức tạp thời gian 1. Sort W, wi > =wj . vs j > i. and change ai ,di 2. T = 0; m = max(di); B[i] = 0, i = 0…m, k = 0. For i = 1 to n do j = di while B[j] > 0 do - - j. if j = 0 then C[k++] = ai . else B[j] = ai . T += wi . Exit for 3. f0 = 0, For i = 1 to m do if B[i] > 0 then B[f0++] = B[i]. 4. B = B +C. Return B, T. O(n.m) O(m) Độ phức tạp O(n.m) O(nlogn)
• 13. tạp thuật toán 4.2 Độ phức tạp không gian 1 mảng lưu n thời hạn kết thúc O(n) 1 mảng lưu n phần thưởng tương ứng O(n) 1 mảng trục thời gian m O(m) 1 mảng lưu công việc trễ k=|m-n| O(k) Độ phức tạp không gian: O(n)
• 14. chương trình • Ngôn ngữ lập trình C++ • Dữ liệu đầu vào • Đầu ra
• 15. chương trình 5.2 So sánh kết quả Thời gian mili giây
• 16. thực tế • Xếp thời gian biểu • Lập lịch cho CPU

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải. Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của ladpro98

include

const int N = 100005; const int INF = N; using namespace std; struct job { int index; int time, limit; } a[N]; int n; bool incTime(const job &a, const job &b) { return a.time < b.time; } bool incLimit(const job &a, const job &b) { return a.limit < b.limit; } struct node { int l, r; int minV, lazy; node *left, *right; node(int l, int _r) {

l = _l; r = _r; minV = INF; lazy = 0; left = right = NULL; } void pushDown() { if (l < r && left == NULL) { left = new node(l, l + r >> 1); right = new node((l + r >> 1) + 1, r); } if (lazy) { minV -= lazy; if (l < r) { left->lazy += lazy; right->lazy += lazy; } lazy = 0; } } void assign(int i, int v) { pushDown(); if (r < i || i < l) return; if (l == r) { minV = v; return; } left->assign(i, v); right->assign(i, v); minV = min(left->minV, right->minV); } void decSuffix(int from, int value) { pushDown(); if (r < from) return; if (from <= l) { lazy += value; pushDown(); return; } left->decSuffix(from, value); right->decSuffix(from, value); minV = min(left->minV, right->minV); } int suffixMin(int from) { pushDown(); if (r < from) return INF; if (from <= l) return minV; return min(left->suffixMin(from), right->suffixMin(from)); } }; struct T_BIT { int bit[N]; T_BIT() { memset(bit, 0, sizeof(bit)); } void update(int i, int v) { for (++i; i < N; i += i & -i) bit[i] += v; } int prefixSum(int i) { int ans = 0; for (++i; i > 0; i -= i & -i) ans += bit[i]; return ans; } } BIT; int order[N]; bool was[N]; int main() { ios::sync_with_stdio(0); cin.tie(0);

ifdef _LAD

freopen("NKTARDY.txt", "r", stdin);

endif // LAD

cin >> n; for (int i = 0; i < n; ++i) a[i].index = i; for (int i = 0; i < n; ++i) cin >> a[i].time; for (int i = 0; i < n; ++i) cin >> a[i].limit; node *root = new node(0, n - 1); sort(a, a + n, incLimit); for (int i = 0; i < n; ++i) order[a[i].index] = i; sort(a, a + n, incTime); vector ans; for (int i = 0; i < n; ++i) { int pos = order[a[i].index]; int minFree = root->suffixMin(pos); int curTime = BIT.prefixSum(pos); if (curTime + a[i].time <= a[i].limit && a[i].time <= minFree) { ans.push_back(a[i]); root->decSuffix(pos, a[i].time); root->assign(pos, a[i].limit - curTime - a[i].time); BIT.update(pos, a[i].time); } } cout << n - ans.size() << endl; for (job it: ans) was[it.index] = 1; sort(ans.begin(), ans.end(), incLimit); for (int i = 0; i < n; ++i) if (!was[a[i].index]) ans.push_back(a[i]); for (job it: ans) cout << it.index + 1 << ' '; return 0; }

Code mẫu của RR

{$R+,Q+}

uses math; const FINP=''; FOUT=''; MAXN=100011; var f1,f2:text; hsize,n:longint; ind,dd,h,d,p:array[1..MAXN] of longint; procedure openF; inline; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; inline; begin close(f1); close(f2); end; procedure inp; inline; var i:longint; begin read(f1,n); for i:=1 to n do read(f1,p[i]); for i:=1 to n do read(f1,d[i]); for i:=1 to n do ind[i]:=i; end; procedure swap(var a,b:longint); inline; var temp:longint; begin temp:=a; a:=b; b:=temp; end; var mid:longint; procedure sort(l,r:longint); inline; var i,j:longint; begin mid:=d[l+random(r-l+1)]; i:=l; j:=r; repeat while d[i]mid do dec(j); if i<=j then begin swap(d[i],d[j]); swap(p[i],p[j]); swap(ind[i],ind[j]); inc(i); dec(j); end; until i>j; if ip[h[j]]) then inc(j); if (p[h[j]]>p[h[i]]) then swap(h[i],h[j]); i:=j; j:=i<<1; end; end; procedure upHeap(i:longint); inline; var j:longint; begin j:=i>>1; while (i>1) and (p[h[i]]>p[h[j]]) do begin swap(h[i],h[j]); i:=j; j:=i>>1; end; end; procedure push(u:longint); inline; begin inc(hsize); h[hsize]:=u; upHeap(hsize); end; procedure pop(var u:longint); inline; begin u:=h[1]; swap(h[1],h[hsize]); dec(hsize); downHeap(1); end; procedure solve; var i,sum,temp:longint; begin hsize:=0; sum:=0; for i:=1 to n do if sum+p[i]<=d[i] then begin sum+=p[i]; dd[i]:=1; push(i); end else if (hsize>0) and (sum-p[h[1]]+p[i]<=d[i]) and (p[h[1]]>p[i]) then begin sum+=p[i]-p[h[1]]; dd[h[1]]:=0; pop(temp); push(i); dd[i]:=1; end; end; begin openF; inp; sort(1,n); solve; ans; closeF; end.

Code mẫu của hieult

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

define fi first

define se second

define PB push_back

define MP make_pair

define ep 0.00000001

define oo 1111111111

define mod 1000000007

define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)

define rep(i, n) for(int i = 0; i < n; i++)

define FOR(i, a, b) for(int i = a; i <= b; i++)

define FORD(i, a, b) for(int i = a; i >= b; i--)

define sz(a) (int)(a.size())

define MS(a, x) memset(a, x, sizeof(a))

//

include

//

define g 9.81

define maxn 100005

double const PI=4*atan(1.0); const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0; char gc() { if (rsz <= 0) { ptr = 0; rsz = fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; } void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); } int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; } template bool gi(T &v) { v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc(); while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true; } using namespace std; typedef pair II; typedef vector VI; typedef vector VII; typedef vector VVI; typedef vector VVII; void OPEN(){ freopen("A.in","r",stdin); freopen("A.out","w",stdout); } struct Work{ int need, finish, id1, id2; Work(){}; bool operator <(Work const w)const{ return finish < w.finish; } }; Work A[100005]; struct comp{ bool operator() (const pair &a, const pair &b) const{ return A[a.fi].need > A[b.fi].need; } }; multiset, comp > S; multiset, comp >::iterator it; int n; int que[100005]; int size = 0, run = 0, fl[100005] = {0}; vector V1, V2; int main(){ // OPEN(); scanf("%d", &n); rep(i, n) scanf("%d", &A[i].need); rep(i, n){ scanf("%d", &A[i].finish); A[i].id1 = i; } sort(A, A + n); rep(i, n) A[i].id2 = i; int t = 0, res = 0, u; rep(i, n){ S.insert(MP(A[i].id2, A[i].id1)); t += A[i].need; while(t > A[i].finish){ it = S.begin(); t -= A[(*it).fi].need; S.erase(it); fl[A[(*it).fi].id1] = 1; } } rep(i, n) { if(fl[A[i].id1]) V2.PB(A[i].id1); else V1.PB(A[i].id1); } printf("%d\n", n - sz(S)); rep(i, sz(V1)) printf("%d ",V1[i] + 1); rep(i, sz(V2)) printf("%d ",V2[i] + 1); }

Code mẫu của ll931110

include

include

include

include

include

include

include

include

include

include

include

include

include

include

typedef long long ll; using namespace std; struct rec { int time,dead,lab; }; bool cmp(rec x,rec y) { return x.dead < y.dead; }; rec a[100010]; bool b[100010]; int t[100010]; int n; bool opt(int x,int y) { return t[x] < t[y]; }; int main() { // freopen("tardy.in","r",stdin); // freopen("tardy.ou","w",stdout); scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i].time); for (int i = 0; i < n; i++) scanf("%d", &a[i].dead); for (int i = 0; i < n; i++) a[i].lab = i; sort(a,a + n,cmp); for (int i = 0; i < n; i++) t[a[i].lab] = a[i].dead; priority_queue< pair > q; int final_time = 0; for (int i = 0; i < n; i++) { q.push(make_pair(a[i].time,a[i].lab)); final_time += a[i].time; while (final_time > a[i].dead) { pair pp = q.top(); q.pop(); final_time -= pp.first; }; }; vector v; while (!q.empty()) { pair pp = q.top(); q.pop(); v.push_back(pp.second); }; sort(v.begin(),v.end(),opt); int ok = v.size(); memset(b,true,sizeof(b)); printf("%d\n", n - ok); for (int i = 0; i < ok; i++) { printf("%d ", v[i] + 1); b[v[i]] = false; }; for (int i = 0; i < n; i++) if (b[i]) printf("%d ", i + 1); };

Code mẫu của khuc_tuan

include

include

include

using namespace std; int n; pair, int> a[100000]; priority_queue > q; bool mark[100000]; int main() { scanf("%d", &n); for(int i=0;ia[i].first.first) { pair p = q.top(); q.pop(); total -= p.first; mark[p.second] = false; } } int dem = 0; for(int i=0;i