Codeforces 191B（贪心)

不念不忘少年蓝@ 2022-06-07 03:43 221阅读 0赞

问题描述:

In the capital city of Berland, Bertown, demonstrations are against the recent election of the King of Berland. Berland opposition, led by Mr. Ovalny, believes that the elections were not fair enough and wants to organize a demonstration at one of the squares.

Bertown has n squares, numbered from 1 to n, they are numbered in the order of increasing distance between them and the city center. That is, square number 1 is central, and square number n is the farthest from the center. Naturally, the opposition wants to hold a meeting as close to the city center as possible (that is, they want an square with the minimum number).

There are exactly k (k < n) days left before the demonstration. Now all squares are free. But the Bertown city administration never sleeps, and the approval of an application for the demonstration threatens to become a very complex process. The process of approval lasts several days, but every day the following procedure takes place:

*  The opposition shall apply to hold a demonstration at a free square (the one which isn't used by the administration).
 *  The administration tries to move the demonstration to the worst free square left. To do this, the administration organizes some long-term activities on the square, which is specified in the application of opposition. In other words, the administration starts using the square and it is no longer free. Then the administration proposes to move the opposition demonstration to the worst free square. If the opposition has applied for the worst free square then request is accepted and administration doesn't spend money. If the administration does not have enough money to organize an event on the square in question, the opposition's application is accepted. If administration doesn't have enough money to organize activity, then rest of administration's money spends and application is accepted
 *  If the application is not accepted, then the opposition can agree to the administration's proposal (that is, take the worst free square), or withdraw the current application and submit another one the next day. If there are no more days left before the meeting, the opposition has no choice but to agree to the proposal of City Hall. If application is accepted opposition can reject it. It means than opposition still can submit more applications later, but square remains free.

In order to organize an event on the square i, the administration needs to spend aibourles. Because of the crisis the administration has only b bourles to confront the opposition. What is the best square that the opposition can take, if the administration will keep trying to occupy the square in question each time? Note that the administration's actions always depend only on the actions of the opposition.

Input

The first line contains two integers n and k — the number of squares and days left before the meeting, correspondingly (1 ≤ k < n ≤ 105).

The second line contains a single integer b — the number of bourles the administration has (1 ≤ b ≤ 1018).

The third line contains n space-separated integers ai — the sum of money, needed to organise an event on square i (1 ≤ ai ≤ 109).

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Output

Print a single number — the minimum number of the square where the opposition can organize the demonstration.

Example

Input

5 2
    8
    2 4 5 3 1

Output

Input

5 2
    8
    3 2 4 1 5

Output

Input

5 4
    1000000000000000
    5 4 3 2 1

Output

题目题意:题目给了我们n个广场，反叛者的活动天数K,政府的总经济b,给了我们n个广场每次租用的花费（其中广场的下标是距离中心城区的远近，下标越小越近),我们需要输出的是反叛者可以租到的距离中心最近的广场的下标。

每一天的活动如下:

反叛者可以租用一个没有被政府使用过的广场

政府为了避免反叛者租到距离中心近的广场，会花钱使用它（干别的),这样政府就有借口不借了，但是如果反叛军租用最后一个（当然是最差的），政府不会花钱使用它的。

政府如果没有钱使用它，那么反叛军就租用成功了，（当然反叛军也可以不使用它，只要他们还有时间)

我们把前面n-1个广场排个序，费用高的在前面，然后累加前面k-1个广场，然后再遍历一遍n个广场。

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define ll long long
    using namespace std;
    
    const int maxn=1e5+10;
    ll a[maxn],b[maxn];
    
    bool cmp(ll a,ll b)
    {
        return a>b;
    }
    int main()
    {
        ll n,k,t;
        cin>>n>>k>>t;
        for (int i=0;i<n;i++) {
            cin>>a[i];
            b[i]=a[i];
        }
        sort (b,b+n-1,cmp);
        ll sum=0;
        for (ll i=0;i<k-1;i++) sum+=b[i];
        for (ll i=0;i<n;i++) {
            if (a[i]>=b[k-1]) {
                if (sum+b[k-1]>t) {//即花费最大的k广场可以花光政府的钱，找最前面那一个
                    cout<<i+1<<endl;
                    return 0;
                }
            }
            else {
              if (a[i]+sum>t) {// 最后一天，我们只要找一个加起来大于t，也可以
                 cout<<i+1<<endl;
                 return 0;
              }
            }
        }
        cout<<n<<endl;
        return 0;
    }