|
3 4 |
|
3 5 |
|
4 2 |
贪心题目,化分离数为块。这里要注意的是 需要进行的排序
以及操作的过程是什么样子的。 感觉那些操作数的问题都是 需要进行排序,然后 根据排序后的数值之差就是操作次数, (i - j + 1) (类似题目: 交换字符)最后 乘以 a[i] 就是将 a[i] 作为目标,然后 - sum 是判断操作次数是否符合规定的操作次数 k 。 如果不符合那么 丢弃前面的选择的元素,所以 j++
- #include
- #include
- #include
- #include
- #include
- #define endl '\n'
- #define x first
- #define y second
- #define int long long
- #define YES puts("YES")
- #define NO puts("NO")
- #define umap unordered_map
- #define All(x) x.begin(),x.end()
- #pragma GCC optimize(3,"Ofast","inline")
- #define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
- using namespace std;
- const int N = 2e6 + 10;
- int n,k;
-
- vector<int>a; // 存储数组
-
- using PII = pair<int,int>;
-
-
- inline void solve()
- {
- cin >> n >> k;
-
- for(int i = 0,x;i < n;++i)
- {
- cin >> x;
- a.emplace_back(x);
- }
-
- // 从小到大的排序。 感觉操作数类的题目都是 需要排一遍数
- // 然后根据位置的下标之差就是需要操作的数,(类似题目: 交换字符)
- // 根据元素位置之差,就是需要添加的数
- sort(All(a));
-
- int sum = 0; // 选取的操作元素
-
- PII ans = {0,0}; // ans.x 总数 ans.y 为 众数
-
- for(int i = 0,j = 0;i < n;++i)
- {
- // 开始选取
- sum += a[i];
-
- // 这里 i - j + 1 是指操作次数
- // * a[i] 这里乘以 a[i] 就是对选取的数值进行操作
- // - sum 就是统计有效的操作数,如果 > k 说明超出了操作数
- // 丢弃前面先选择的 小的数
- while((i - j + 1) * a[i] - sum > k) sum -= a[j++];
-
- // 如果操作后的该元素的众数比之前的多,那么更新答案
- if(ans.x < (i - j + 1)) ans = {i - j + 1,a[i]};
- }
-
- cout << ans.x << ' ' << ans.y << endl;
-
- }
-
-
- signed main()
- {
- // freopen("a.txt", "r", stdin);
- ___G;
- int _t = 1;
- // cin >> _t;
- while (_t--)
- {
- solve();
- }
-
- return 0;
- }