Cặp nhóm
Xem dạng PDF
Mã bài:
capjnhom
Điểm:
2 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
512M
Dữ liệu vào:
stdin
Dữ liệu ra:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, Python, Scratch
Cho dãy số nguyên dương gồm n số a1,a2,...,an. Tìm cách xếp n số này thành ít nhóm nhất thỏa mãn hai điều kiện sau:
- Mỗi nhóm có ít nhất một số và nhiều nhất hai số.
- Tổng các số trong cùng một nhóm không vượt quá m.
Dữ liệu vào từ tệp văn bản CAU5.INP gồm 2 dòng
- Dòng 1: gồm 2 số n và m (1≤n≤10$^5$;m≤10$^9$ ).
- Dòng 2: gồm n số a1,a2,...,an (0<ai≤m).</li>
Kết quả ghi vào tệp văn bản CAU5.OUT một số duy nhất chứa một số là số nhóm ít nhất.
Ví dụ:
| input | output |
|---|---|
| 4 135 50 74 60 82 |
2 |
| 6 135 50 120 74 60 100 82 |
4 |
Bình luận
include<bits/stdc++.h>
define ll long long
using namespace std; ll n,i; ll a[100005]; map<ll,ll> ts; map<ll,bool> daIn; int main() { iosbase::syncwith_stdio(0); cin.tie(0);cout.tie(0); freopen("a.inp","r",stdin); freopen("a.out","w",stdout); cin>>n; for(i=1;i<=n;i++) { cin>>a[i]; ts[a[i]]++; } for(i=1;i<=n;i++) { ll x=a[i]; if(ts[x]>0) { cout<<x<<" "<<ts[x]<<"\n"; ts[x]=0; } } return 0; }
include<bits/stdc++.h>
using namespace std; map<int,int> m; int i,n,x,a[10000007],d[10000000]; int main() { iosbase::syncwith_stdio(0); cin.tie(0);cout.tie(0); freopen("hello.inp","r",stdin); freopen("hello.out","w",stdout); cin>>n; for(i=1;i<=n;i++) { cin>>a[i]; d[a[i]]++; } for(i=1;i<=n;i++) { if(d[a[i]]>0) { cout<<a[i]<<" "<<d[a[i]]<<'\n'; d[a[i]]=0; }
}
hello