10000 solved 0x13 1654 · jo0n-lab/basic-algo-lecture@fdeb2b9 · GitHub
[go: up one dir, main page]
Skip to content

Commit fdeb2b9

Browse files
author
cuberry
committed
solved 0x13 1654
1 parent bed09ad commit fdeb2b9

File tree

13 files changed

+113
-0
lines changed

13 files changed

+113
-0
lines changed

‎0x13/README.md

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
최적화 문제: N 개를 만들 수 있는 랜선의 최대 길이
2+
결정 문제: 랜선의 길이가 X일 때, 랜선이 N개 이상인가 아닌가?
3+
4+
5+
lower bound: 찾고자 하는 값 이상이 처음 나타나는 위치
6+
upper bound: 찾고자 하는 값 초과가 처음 나타나는 위치

‎0x13/lower_bound/main

24 KB
Binary file not shown.

‎0x13/lower_bound/main.cc

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
#include<bits/stdc++.h>
2+
using namespace std;
3+
4+
int arr[102];
5+
int N,target;
6+
7+
int main(){
8+
ios::sync_with_stdio(false);
9+
cin.tie(NULL);
10+
11+
cin>>N;
12+
for(int i=1;i<=N;i++)
13+
cin>>arr[i];
14+
sort(arr+1,arr+N+1);
15+
cin>>target;
16+
17+
18+
int st=1;
19+
int en=N;
20+
int mid;
21+
while(st<en){
22+
mid=(st+en)/2;
23+
if(arr[mid]<target)
24+
st=mid+1;
25+
else
26+
en=mid;
27+
}
28+
cout<<arr[mid]<<" "<<mid;
29+
}
30+
31+
32+
33+

‎0x13/lower_bound/tc1

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
5
2+
1 3 5 7 7
3+
7

‎0x13/lower_bound/tc2

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
8
2+
1 2 3 5 7 9 11 15
3+
6

‎0x13/lower_bound/tc3

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
5
2+
1 2 3 4 5
3+
7

‎0x13/lower_bound/tc4

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
8
2+
1 2 3 5 7 9 11 15
3+
18

‎0x13/1654/1654.cpp renamed to ‎0x13/v1654/1654.cpp

File renamed without changes.

‎0x13/v1654/main

16.5 KB
Binary file not shown.

‎0x13/v1654/main.cc

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
#include <bits/stdc++.h>
2+
using namespace std;
3+
4+
// #define __INPUT__
5+
// #define __PRNIT__
6+
// #define __DEBUG__
7+
8+
int N, K;
9+
int arr[10002];
10+
11+
long long step(long long x) {
12+
long long cur = 0;
13+
for (int i = 1; i <= K; i++)
14+
cur += arr[i] / x;
15+
return cur;
16+
}
17+
18+
int main() {
19+
ios::sync_with_stdio(false);
20+
cin.tie(NULL);
21+
22+
cin >> K >> N;
23+
for (int i = 1; i <= K; i++)
24+
cin >> arr[i];
25+
26+
long long st = 1;
27+
long long en = 0x7fffffff;
28+
long long mid;
29+
30+
while (st < en) {
31+
mid = (st + en + 1) / 2;
32+
#ifdef __DEBUG__
33+
cout << "mid " << mid << " ";
34+
#endif
35+
long long cur = step(mid);
36+
if (cur < N)
37+
en = mid - 1;
38+
else
39+
st = mid;
40+
#ifdef __DEBUG__
41+
cout << "cur " << cur << " ";
42+
cout << "st " << st << " en " << en << " ";
43+
cout << "st val " << step(st) << " en val " << step(en) << "\n";
44+
#endif
45+
}
46+
47+
cout << st;
48+
}

0 commit comments

Comments
 (0)
0