fork download 
  1. /*
  2.     Cred : SunnyYeahBoi
  3.     It's my last chance (⌐■_■)
  4.     Problem :
  5. */
  6.  
  7. #include<bits/stdc++.h>
  8.  
  9. using namespace std;
  10.  
  11. #define int long long
  12. #define double long double
  13. #define endl "\n"
  14. #define NAME "a"
  15.  
  16. const int MAXN = 1e6 + 5;
  17. const int inf = 1e18;
  18. const int MOD = 1e9 + 7;
  19.  
  20. void FileInput(){
  21.     if(fopen(NAME".inp" , "r") == NULL)
  22.         freopen(NAME".inp" , "w" , stdout);
  23.     freopen(NAME".inp" , "r" , stdin);
  24.     freopen(NAME".out" , "w" , stdout);
  25. }
  26.  
  27. /*
  28.     Chọn ra k số 
  29.     trừ đi từng số vào x
  30.     ai
  31.     x -= ai
  32.     tìm k nhỏ nhất sao cho x âm 
  33.  
  34.     Tham lam 
  35.     Yêu cầu: chọn ra k số sao cho tổng > x
  36.  
  37.     độ lớn => cứ chọn số lớn nhất
  38.  
  39.     đáp án: lấy tổng các số lớn nhất cho tới tổng > x
  40.  
  41.     sort lại theo thứ tự tăng dần 
  42.     a1 <= a2 <= a3 <= .... <= an
  43.     tong = 0
  44.     k = 0
  45.     while(tong <= x)
  46.         tong += a[n]
  47.         n--
  48.         k++
  49.  
  50.     sort theo thứ tự giảm dần => số lớn nhất ở vị trí 1  
  51.     lấy k số đầu tiên
  52.     a1 >= a2 >= a3 ... >= an 
  53. */
  54.  
  55. int n , x;
  56. int a[MAXN];
  57.  
  58. void solve(){
  59.     cin >> n >> x;
  60.     for(int i = 1 ; i <= n ; i++)
  61.         cin >> a[i];
  62.  
  63.     sort(a + 1 , a + 1 + n , greater<int>()); // thay đổi phép so sánh 
  64.  
  65.     int tong = 0; 
  66.     bool flag = false; // biến cờ hiệu - có tìm ra kết quả không?
  67.     for(int i = 1 ; i <= n ; i++){
  68.         tong += a[i];
  69.         if(tong > x){
  70.             cout << i << endl;
  71.             flag = true;
  72.             break;
  73.         }
  74.     }
  75.  
  76.     if(flag == false) cout << -1 << endl;
  77. }
  78.  
  79. int32_t main(){
  80.     //FileInput();
  81.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  82.     int t = 1;
  83.     // cin >> t;
  84.     while(t--)
  85.         solve();
  86.     return 0;
  87. }
  88.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin 
Standard input is empty
stdout 
-1
https://ideone.com/K1P16n
language:
C++14 (gcc 8.3)
created:
17 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!