生活随笔
收集整理的這篇文章主要介紹了
Half of Same 思维，模拟，调试
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
題意 ：
- 給一序列，每次操作可以讓一個元素減去k（k>=1），求最大的k使得若干次操作后序列中至少一半元素相等，若k為任意大，則輸出-1
思路 ：
- 首先枚舉任意兩個數的差，那么答案k一定存在于這些差的因數中，所以枚舉每組差的因數，以當前差的被減數為媒介（最終至少一半數等于這個數）判斷當前k是否滿足條件，取滿足的最大值
- 特別地，當原序列中有一個元素已經大于等于元素的個數的一半（n為奇數是(n+1)/2，n為偶數是n/2，但由于向下取整，可以統一為（n+1)/2），那么k為任意大，輸出-1
#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_map>
#define debug(a) cout << #a << " = " << a << endl;
#define x first
#define y second
using namespace std
;
typedef long long ll
;const int N
= 50;int n
;
int a
[N
];int update(int dif
, int x
)
{int k
= 0;for (int i
= 1; i
* i
<= dif
; i
++ ){if (dif
% i
) continue;int cnt
= 0;for (int j
= 1; j
<= n
; j
++ )if (abs(a
[j
] - x
) % i
== 0) cnt
++ ;if (cnt
>= (n
+ 1) / 2) k
= max(k
, i
);cnt
= 0;for (int j
= 1; j
<= n
; j
++ )if (abs(a
[j
] - x
) % (dif
/ i
) == 0) cnt
++ ;if (cnt
>= (n
+ 1) / 2) k
= max(k
, dif
/ i
);}return k
;
}int main()
{ios
::sync_with_stdio(false); cin
.tie(0); cout
.tie(0);int _
;cin
>> _
;while (_
-- ){unordered_map
<int, int> ma
;cin
>> n
;for (int i
= 1; i
<= n
; i
++ ) cin
>> a
[i
], ma
[a
[i
]] ++ ;bool flag
= false;for (auto i
: ma
)if (i
.second
>= (n
+ 1) / 2){flag
= true;break;}if (flag
){cout
<< -1 << endl
;continue;}int k
= 0;for (int i
= 1; i
<= n
; i
++ )for (int j
= i
+ 1; j
<= n
; j
++ ){int dif
= abs(a
[i
] - a
[j
]);if (dif
== 0) continue; k
= max(k
, update(dif
, a
[i
]));
}cout
<< k
<< endl
;}return 0;
}
總結
以上是生活随笔為你收集整理的Half of Same 思维，模拟，调试的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
