• G. The Great Equalizer


    Problem - G - Codeforces

    思路:通过它给定的这个操作,我们能够发现操作的本质,在排序后,其实每次操作之后,都会把相邻的两个数的差值减少1,所以最大的操作次数就是相邻的最大的差值,并且这个是可以用set维护出来的,但是知道了最大的差值怎么求出变化后的值一直没想出来,看了题解发现自己很蠢,那么很明显能够发现最大值每次都在加一,那么最后的答案就是相邻的最大差值+在放入平衡器之前的最大值

    1. // Problem: G. The Great Equalizer
    2. // Contest: Codeforces - Codeforces Round 894 (Div. 3)
    3. // URL: https://codeforces.com/contest/1862/problem/G
    4. // Memory Limit: 256 MB
    5. // Time Limit: 4000 ms
    6. #include
    7. #include
    8. #include
    9. #define fi first
    10. #define se second
    11. #define i128 __int128
    12. using namespace std;
    13. typedef long long ll;
    14. typedef double db;
    15. typedef pair<int,int> PII;
    16. const double eps=1e-7;
    17. const int N=5e5+7 ,M=5e5+7, INF=0x3f3f3f3f,mod=1e9+7,mod1=998244353;
    18. const long long int llINF=0x3f3f3f3f3f3f3f3f;
    19. inline ll read() {ll x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
    20. while(c>='0'&&c<='9') {x=(ll)x*10+c-'0';c=getchar();} return x*f;}
    21. inline void write(ll x) {if(x < 0) {putchar('-'); x = -x;}if(x >= 10) write(x / 10);putchar(x % 10 + '0');}
    22. inline void write(ll x,char ch) {write(x);putchar(ch);}
    23. void stin() {freopen("in_put.txt","r",stdin);freopen("my_out_put.txt","w",stdout);}
    24. bool cmp0(int a,int b) {return a>b;}
    25. template<typename T> T gcd(T a,T b) {return b==0?a:gcd(b,a%b);}
    26. template<typename T> T lcm(T a,T b) {return a*b/gcd(a,b);}
    27. void hack() {printf("\n----------------------------------\n");}
    28. int T,hackT;
    29. int n,m,k;
    30. int w[N];
    31. void solve() {
    32. n=read();
    33. for(int i=1;i<=n;i++) w[i]=read();
    34. if(n==1) {
    35. m=read();
    36. while(m--) {
    37. int x=read(),c=read();
    38. printf("%d ",c);
    39. }
    40. printf("\n");
    41. return ;
    42. }
    43. set<int> s;
    44. map<int,int> cnt;
    45. for(int i=1;i<=n;i++) {
    46. cnt[w[i]]++;
    47. if(cnt[w[i]]==1) s.insert(w[i]);
    48. }
    49. priority_queue<int,vector<int>,less<int> > q;
    50. map<int,int> st;
    51. int last=-1;
    52. for(auto &it:s) {
    53. if(last==-1) last=it;
    54. else {
    55. int t=it-last;
    56. q.push(t);
    57. last=it;
    58. }
    59. }
    60. m=read();
    61. while(m--) {
    62. int x=read(),c=read();
    63. int k=w[x];
    64. cnt[k]--;
    65. if(cnt[k]==0) {
    66. auto it=s.lower_bound(k);
    67. int tit=*it;
    68. if(it==s.begin()) {
    69. int l=*it;
    70. it++;
    71. int r=*it;
    72. st[r-l]++;
    73. }else {
    74. auto it1=it,it2=it;
    75. it1--;
    76. it2++;
    77. if(it2==s.end()) {
    78. int a=*it1,b=*it;
    79. st[b-a]++;
    80. }else {
    81. int a=*it1,b=*it,c=*it2;
    82. st[b-a]++;
    83. st[c-b]++;
    84. q.push(c-a);
    85. }
    86. }
    87. s.erase(s.lower_bound(tit));
    88. }
    89. cnt[c]++;
    90. w[x]=c;
    91. if(cnt[c]==1) {
    92. auto t1=s.lower_bound(c);
    93. if(t1==s.end()) {
    94. auto it1=t1;
    95. it1--;
    96. int ta=*it1,tb=c;
    97. q.push(tb-ta);
    98. s.insert(c);
    99. }else {
    100. if(t1==s.begin()) {
    101. int ta=c,tb=*t1;
    102. q.push(tb-ta);
    103. s.insert(c);
    104. }else {
    105. auto it1=t1,it2=t1;
    106. it1--;
    107. int ta=*it1,tb=c,tc=*it2;
    108. q.push(tb-ta),q.push(tc-tb);
    109. st[tc-ta]++;
    110. s.insert(c);
    111. }
    112. }
    113. }
    114. while(q.size()&&st[q.top()]!=0) {
    115. st[q.top()]--;
    116. q.pop();
    117. }
    118. auto t=s.rbegin();
    119. int tk=0;
    120. if(q.size()) tk=q.top();
    121. printf("%d ",*t+tk);
    122. }
    123. printf("\n");
    124. }
    125. int main() {
    126. // init();
    127. // stin();
    128. // ios::sync_with_stdio(false);
    129. scanf("%d",&T);
    130. // T=1;
    131. while(T--) hackT++,solve();
    132. return 0;
    133. }

  • 相关阅读:
    【docker】docker启动neo4j,并配置内存
    SSM框架速成3:SpringMVC
    Go:Gnome sort 侏儒排序(附完整源码)
    ubuntu20编译安装pkg-config
    torch中tensor的相关操作
    1.6 Go微服务实战(Go语言基础) --- 包和代码测试
    Task07|缺失数据|DataWhale组队学习
    淘宝用户购物行为数据分析
    目标检测(Object Detection)概念速通
    python-线程池的使用
  • 原文地址:https://blog.csdn.net/zzzyyzz_/article/details/132862729