传送门：点击打开链接
题意：一个人手上有s卢布，他要在n天内买m样东西中的k样
样例第二行是多少卢布换一美刀，第三行是多少卢布换一英镑
然后接下来是m样东西，告诉你每样东西用什么货币结账（1是美刀，2是卢布），以及要多少那种外币
要求：最早完成买k样的天数，以及输出方案
输出第几天买完k样商品，然后k行
购买的商品的id，第几天购买的
输出任意答案就可以了
一种商品只能购买一次，但是一天可以买多种商品
思路：对于前i天购买东西，肯定是选择在1天内或者2天内买完，就是汇率最高的时候购买。
对于某一天，我们能用O(n)的复杂度来求出当前最低所需要的钱来买k件商品，这里面只要把商品按照购买方式分类，然后排序一遍，之后就很好维护了。
那么对于前i天，很明显这个有单调性，先求出前i天里面两种汇率最大的分别是哪两天，预处理一下，之后只要二分i，就能得到答案了
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;
typedef pair<int, int>PII;const int MX = 2e5 + 5;
const int INF = 0x3f3f3f3f;PII S1[MX], S2[MX];
int n, m, k; LL s;
vector<PII>A1, A2;bool check(int x, bool print = false) {int l = k - min(k, (int)A2.size());int r = min(k, (int)A1.size()), pos = -1;LL a = S1[x].first, b = S2[x].first;LL sum = 0;for(int i = 1; i <= l; i++) sum += a * A1[i - 1].first;for(int i = 1; i <= k - l; i++) sum += b * A2[i - 1].first;for(int i = l; i <= r; i++) {if(sum <= s) {pos = i; break;}if(i == r) break;sum += a * A1[i].first;sum -= b * A2[k - i - 1].first;}if(pos == -1) return false;if(!print) return true;printf("%d\n", x);for(int i = 1; i <= pos; i++) printf("%d %d\n", A1[i - 1].second, S1[x].second);for(int i = 1; i <= k - pos; i++) printf("%d %d\n", A2[i - 1].second, S2[x].second);return true;
}void solve() {int l = 1, r = n, mid;if(!check(r)) {printf("-1\n");return;}while(l <= r) {mid = (l + r) >> 1;if(check(mid)) r = mid - 1;else l = mid + 1;}check(r + 1, true);
}int main() {//FIN;while(~scanf("%d%d%d%I64d", &n, &m, &k, &s)) {A1.clear(); A2.clear();S1[0] = S2[0] = PII(INF, INF);for(int i = 1; i <= n; i++) {PII temp;temp.second = i;scanf("%d", &temp.first);S1[i] = min(S1[i - 1], temp);}for(int i = 1; i <= n; i++) {PII temp;temp.second = i;scanf("%d", &temp.first);S2[i] = min(S2[i - 1], temp);}for(int i = 1; i <= m; i++) {PII temp; int id;temp.second = i;scanf("%d%d", &id, &temp.first);if(id == 1) A1.push_back(temp);else A2.push_back(temp);}sort(A1.begin(), A1.end());sort(A2.begin(), A2.end());solve();}return 0;
}