| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
NKBUS - Bus |
Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/nkbus
Một xe buýt của công ty có nhiệm vụ đón nhân viên đến trụ sở làm việc. Trên hành trình, xe buýt sẽ tiếp nhận nhân viên đứng chờ ở các điểm hẹn nếu như xe còn chỗ trống. Xe buýt có thể đỗ lại để chờ những công nhân chưa kịp đến điểm hẹn.
Cho biết thời điểm mà mỗi nhân viên đến điểm hẹn của mình và thời điểm qua mỗi điểm hẹn của xe buýt. Giả thiết rằng xe buýt đến điểm hẹn đầu tiên tại thời điểm 0 và thời gian xếp khách lên xe được bằng 0.
Xe buýt cần phải chở một số lượng nhiều nhất các nhân viên có thể được đến trụ sở. Hãy xác định khoảng thời gian ngắn nhất để xe buýt thực hiện công việc.
Dữ liệu vào
Dòng đầu tiên chứa 2 số nguyên dương n, m theo thứ tự là số điểm hẹn và số chỗ ngồi của xe buýt
Dòng thứ i trong số n dòng tiếp theo chứa số nguyên ti là thời gian cần thiết để xe buýt di chuyển từ điểm hẹn thứ i đến điểm hẹn thứ i+1 (điểm hẹn thứ n+1 sẽ là trụ sở làm việc của công ty) và số nguyên k là số lượng nhân viên đến điểm hẹn i, tiếp theo k số nguyên là các thời điểm đến điểm hẹn của k nhân viên.
Kết qủa
Gồm một dòng duy nhất, là thời gian ngắn nhất tìm được.
Giới hạn
1 ≤ n ≤ 200000, 1 ≤ m ≤ 20000
Tổng số nhân viên không vượt quá 200000.
Kết quả không vượt quá 231-1.
Ví dụ
Dữ liệu mẫu 3 2 3 2 4 3 1 3 6 3 7 5 1 5 Kết qủa 10
Giải thích: Trên đường đến công ty có 3 trạm xe buýt. Từ trạm 1 đến trạm 2, trạm 2 đến trạm 3, và từ trạm 3 đến công ty lần lượt mất 3, 1 và 5 đơn vị thời gian. Xe buýt có thể đi như sau: đến thẳng trạm 2, đón người thứ 2, đến trạm 3, chờ 1 đơn vị thời gian để đón người duy nhất ở trạm này, và cuối cùng đến công ty. Tổng cộng xe buýt đi mất 3 + 1 + 1 + 5 = 10 đơn vị thời gian.
| Được gửi lên bởi: | Jimmy |
| Ngày: | 2007-11-30 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET |
| Nguồn bài: | Adapted from Ukrainian OI 2000 |
hide comments
|
|||||||||||||
|
2021-11-09 04:34:37
1 ←Total test case T 3 2 ← Starting testcase 1 1 2 2 3 Output #1 010 |
|||||||||||||
|
2021-11-09 04:34:23
Level 4 Map Coloring We consider a geographical map with N countries numbered from 1 to N (1 <= N <= 1000). For every country we know the numbers of other countries which are connected with its border. From every country we can reach to any other one, eventually crossing some borders. Write a program which determines whether it is possible to color the map only in two colors-red and blue in such a way that if two countries are connected their colors are different. The color of the first country is red. Your program must output one possible coloring for the other countries, or show, that such coloring is impossible. [Input] The first line is the total number of test cases T. A test case has two lines. In each test case, the first line has N (the number of countries) and E (the number of border) separated by a space. The next line enumerates E border. A border consists of the two countries it connects. For example, the border connecting countries 5 and 28 is represented by “5 28” or “28 5”. The indices of countries are 1 through N. All adjacent numbers in a line are each separated by a space. [Output] Output the each answer in 1 line. Each line starts with ‘#x’, where x means the index of a test case, and puts a space, and prints the answer. If the coloring is possible, this answer must contain a list of zeros and ones, without any separators between them. The i-th digit in this sequence is the color of the i-th country. 0 corresponds to red color, and one - to blue color. If a coloring is not possible, output the integer −1. |
|||||||||||||
|
2021-11-09 04:33:56
Level 4 Map Coloring We consider a geographical map with N countries numbered from 1 to N (1 <= N <= 1000). For every country we know the numbers of other countries which are connected with its border. From every country we can reach to any other one, eventually crossing some borders. Write a program which determines whether it is possible to color the map only in two colors-red and blue in such a way that if two countries are connected their colors are different. The color of the first country is red. Your program must output one possible coloring for the other countries, or show, that such coloring is impossible. [Input] The first line is the total number of test cases T. A test case has two lines. In each test case, the first line has N (the number of countries) and E (the number of border) separated by a space. The next line enumerates E border. A border consists of the two countries it connects. For example, the border connecting countries 5 and 28 is represented by “5 28” or “28 5”. The indices of countries are 1 through N. All adjacent numbers in a line are each separated by a space. [Output] Output the each answer in 1 line. Each line starts with ‘#x’, where x means the index of a test case, and puts a space, and prints the answer. If the coloring is possible, this answer must contain a list of zeros and ones, without any separators between them. The i-th digit in this sequence is the color of the i-th country. 0 corresponds to red color, and one - to blue color. If a coloring is not possible, output the integer −1. |
|||||||||||||
|
2021-11-08 18:43:30
Last edit: 2021-11-09 04:33:27 |
|||||||||||||
|
2021-11-08 11:04:26
7 8 1 3 5 4 1 4 6 6 2 0 1 1 1 3 1 3 3 6 3 4 7 4 6 1 4 6 5 4 6 7 7 6 3 2 5 0 3 3 3 6 7 3 2 5 1 0 5 7 5 4 3 4 6 5 5 3 3 5 1 9 7 2 1 6 6 2 0 2 0 6 0 0 6 5 2 1 2 6 6 5 1 4 5 7 4 2 4 0 6 0 3 4 0 7 2 3 1 2 6 2 1 5 1 3 7 2 0 2 1 2 1 2 5 1 4 0 6 5 1 5 1 0 2 2 1 4 3 8 6 2 0 5 7 4 6 6 5 4 6 6 3 7 7 1 1 7 1 7 1 5 1 6 5 4 6 2 2 6 5 0 4 7 2 7 2 7 0 1 4 3 3 1 2 6 3 4 6 4 4 5 9 10 7 1 9 4 1 6 5 7 2 2 4 4 7 3 0 5 0 3 7 5 6 1 5 2 5 0 7 3 0 1 7 4 6 7 0 0 4 1 5 6 3 5 5 7 3 3 2 7 0 0 2 2 4 4 6 1 5 6 1 5 0 6 2 4 6 3 6 1 6 7 7 0 4 7 2 2 0 7 0 6 2 6 3 1 5 6 4 0 1 6 2 3 5 10 8 5 1 7 4 5 3 0 0 6 3 5 5 0 1 5 7 7 2 1 6 5 0 2 1 5 0 4 1 2 1 5 0 1 0 4 1 2 2 5 1 0 1 4 6 1 3 7 7 4 7 1 5 5 2 5 1 3 1 0 6 1 0 2 7 6 2 5 4 7 2 7 1 3 1 5 0 0 0 1 1 4 1 6 17 18 8 6 2 0 4 6 1 1 7 2 5 2 4 3 4 7 5 0 2 6 1 1 2 1 2 6 0 2 3 1 6 7 2 1 5 6 2 0 6 2 4 7 1 6 7 1 6 1 5 6 3 4 0 1 6 0 5 3 2 3 7 1 7 4 7 4 5 5 3 0 1 1 5 7 4 6 6 6 0 4 3 0 5 6 6 2 3 1 7 0 0 3 5 6 4 6 7 0 3 5 0 6 2 6 3 2 6 1 3 4 2 0 7 0 0 7 4 6 2 5 2 3 0 3 3 6 4 5 2 6 5 7 1 2 1 3 5 0 7 0 6 2 3 4 1 5 3 5 0 4 2 4 6 6 3 3 3 3 1 0 6 4 4 3 4 3 6 5 4 1 6 2 5 7 5 0 2 7 7 0 5 4 5 4 1 7 1 2 4 4 1 0 5 4 7 0 3 4 0 6 7 5 4 0 2 5 6 5 1 7 5 1 0 6 1 0 5 0 1 1 7 1 5 5 7 4 0 7 5 2 0 6 6 4 1 1 4 3 7 3 7 3 3 0 3 2 7 6 2 7 5 7 3 1 5 6 2 6 5 7 2 6 7 5 1 6 5 6 4 1 0 1 2 4 1 4 5 1 7 7 6 6 3 5 0 6 0 3 0 1 0 1 3 0 2 2 1 4 0 7 1 7 0 0 5 2 1 5 6 |
|||||||||||||
|
2021-11-08 09:11:08
public static boolean check( int i, int j) { if(a[i][j]==1) { if(a[i][j-1]==3||a[i][j+1]==3||a[i+1][j]==4||a[i+1][j]==7||a[i-1][j]==5||a[i-1][j]==6||a[i-1][j]==1||a[i+1][j]==1||a[i][j-1]==1||a[i][j+1]==1||a[i-1][j]==2||a[i+1][j]==2||a[i][j-1]==5||a[i][j+1]==6) return true; } else if (a[i][j]==2) { if(a[i-1][j]==1||a[i+1][j]==1||a[i-1][j]==2||a[i+1][j]==2||a[i+1][i]==4||a[i+1][j]==7||a[i-1][j]==5||a[i-1][j]==6) { return true; } } else if (a[i][j]==3) { if(a[i][j-1]==1||a[i][j+1]==1||a[i][j-1]==3||a[i][j+1]==3||a[i][j-1]==4||a[i][j-1]==5||a[i][j+1]==6||a[i][j+1]==7) { return true; } } else if (a[i][j]==4) { if(a[i][j+1]==1||a[i-1][j]==1||a[i-1][j]==2||a[i][j+1]==3||a[i-1][j]==5||a[i-1][j]==6||a[i][j+1]==6||a[i][j+1]==7) { return true; } } else if (a[i][j]==5) { if(a[i+1][j]==1||a[i][j+1]==1||a[i+1][j]==2||a[i][j+1]==3||a[i+1][j]==4||a[i][j+1]==6||a[i+1][j]==7||a[i][j+1]==7) { return true; } } else if (a[i][j]==6) { if(a[i+1][j]==1||a[i][j-1]==1||a[i+1][j]==2||a[i][j-1]==3||a[i+1][j]==4||a[i][j-1]==4||a[i][j-1]==5||a[i][j-1]==7) { return true; } } else if (a[i][j]==7) { if(a[i-1][j]==1||a[i][j-1]==1||a[i-1][j]==2||a[i][j-1]==3||a[i][j-1]==4||a[i-1][j]==5||a[i][j-1]==5||a[i-1][j]==6) { return true; } } return false; } |
|||||||||||||
|
2021-11-08 09:10:34
5 6 2 1 3 => The size of the map is 5 x 6, starting point is (2,1), the limit of pump is 3 0 0 5 3 6 0 => The first row of the map 0 0 2 0 2 0 => The second row of the map 3 3 1 3 7 0 0 0 0 0 0 0 0 0 0 0 0 0 5 6 2 2 6 3 0 0 0 0 3 2 0 0 0 0 6 1 3 1 1 3 1 2 0 2 0 0 2 0 0 4 3 1 1 10 10 4 3 9 0 0 0 0 0 0 0 0 0 0 0 0 0 7 5 0 5 0 0 0 0 0 3 2 2 6 0 0 0 0 0 4 7 2 2 2 7 0 0 4 0 3 0 1 1 2 2 0 0 5 0 5 6 1 1 1 1 6 2 5 7 4 1 2 0 0 4 6 0 0 5 3 1 7 0 2 2 6 5 7 7 3 2 1 1 7 1 0 2 7 3 4 0 0 4 0 5 1 0 1 |
|||||||||||||
|
2021-11-08 05:10:58
package battlecity; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class BattleCity { static int queue[] = new int [1000000]; public static void main(String[] args) throws FileNotFoundException { System.setIn(new FileInputStream("C:\\Users\\Administrator\\eclipse-workspace\\Practice\\src\\battlecity\\input.txt")); Scanner scanner = new Scanner(System.in); int testcase; int dx[] = {0, 1, 0, -1}; int dy[] = {1, 0, -1, 0}; testcase = scanner.nextInt(); for (int t = 0; t < testcase; t++) { int soHang; int soCot; soHang = scanner.nextInt(); soCot = scanner.nextInt(); char maTran[][] = new char[soHang][soCot]; int map[][] = new int [soHang][soCot]; int visited[][] = new int[soHang][soCot]; String chuoi[] = new String[soHang]; for (int c = 0; c < soHang; c++) { chuoi[c] = scanner.next(); } int xStart = 0; int yStart = 0; int xEnd = 0; int yEnd = 0; // nhap du lieu for (int h = 0; h < soHang; h++) { for (int c = 0; c < soCot; c++) { maTran[h][c] = chuoi[h].charAt(c); visited[h][c] = 0; if (maTran[h][c] == 'Y') { map[h][c] = 1; xStart = h; yStart = c; } else if (maTran[h][c] == 'T') { map[h][c] = 1; xEnd = h; yEnd = c; } else if (maTran[h][c] == 'S' || maTran[h][c] == 'R') { map[h][c] = -1; } else if (maTran[h][c] == 'E') { map[h][c] = 1; } else if (maTran[h][c] == 'B') { map[h][c] = 2; } } } //xu ly int dau = 0; int cuoi = 0; queue[cuoi] = xStart * 1000 + yStart; cuoi = 1; visited[xStart][yStart] = 1; while (dau != cuoi) { int x = queue[dau] / 1000; int y = queue[dau] % 1000; if (x == xEnd && y == yEnd) { dau++; continue; } for (int i = 0; i < 4; i++) { int hang = x + dx[i]; int cot = y + dy[i]; if (hang >= 0 && hang < soHang && cot >=0 && cot < soCot && map[hang][cot] != -1) { if (visited[hang][cot] == 0) { // tai vi tri chua tham thi them vao queue queue[cuoi] = hang * 1000 + cot; visited[hang][cot] = visited[x][y] + map[hang][cot]; cuoi++; } else { if (visited[hang][cot] > visited[x][y] + map[hang][cot]) { queue[cuoi] = hang * 1000 + cot; cuoi++; visited[hang][cot] = visited[x][y] + map[hang][cot]; } } } } dau++; } System.out.println("Case #" + (t + 1)); System.out.println((visited[xEnd][yEnd] - 1)); } } } |
|||||||||||||
|
2021-11-04 11:19:17
10 3 7 2 1 5 1 2 2 2 4 10 10 2 1 5 1 2 2 2 9 11 10 10 0 0 0 0 0 0 0 0 0 0 1 10 10 10 10 10 10 10 10 10 10 10 1 1 0 1 10 1 2 3 4 5 6 7 8 9 10 10 10 10 9 8 7 6 5 4 3 2 1 9 10 1 2 3 4 5 6 7 8 9 10 3 10 20 19 18 17 16 15 14 13 12 11 14 100 1 2 3 4 5 6 7 8 9 0 11 22 33 44 55 66 77 88 99 12 12 13 14 15 16 17 18 19 10 0 9 12 12 34 23 25 27 28 29 10 10 1 2 3 4 5 6 7 8 9 0 99 12 12 13 14 15 16 17 18 19 77 88 99 12 12 13 14 15 16 17 29 10 10 1 2 3 4 5 6 7 12 13 14 15 16 17 18 19 20 23 24 25 26 2 3 41 8 0 10 |
|||||||||||||
|
2021-11-04 10:26:12
package spoj; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class Solution { public static void main(String[] args) throws FileNotFoundException { Scanner sc =new Scanner(new FileInputStream("D:\\trung.txt")); int T; T=sc.nextInt(); for(int test=1;test<=T;test++) { int n; int k; k=sc.nextInt(); n=sc.nextInt(); int a[]= new int [1000000]; for(int i = 0; i<n; i++) { a[i]=sc.nextInt(); } int max = 0; for(int i = 0; i < n; i++) { if(a[i] > max) max = a[i]; } while(true) { int sum = 0; int b = 1; for(int i = 0; i < n; i++) { sum+= a[i]; if(sum > max) { b++; sum = a[i]; } } if(b<=k) break; max++; } System.out.println(max); } } } |
|||||||||||||
RSS