傳送門

?題意

給k個數列，從中k個數列中找出任意2個數列 i ,j

使得數列i刪除第x個數，和數列j刪除第y個數的和相等

若存在，輸出 i ,x 和 j,y?

?思路

每個數列之間的聯系為數列的和之間的差det

如果開二維數組記錄每個數列之間的det的話，顯然是不可行的_(:з」∠)_

這里用map<x ,pair<i ,j > >mp表示序列 i 刪除第 j 個數后的總和為 x；

如果某兩個序列各刪除一個數，得到的總和相等，

也就是后一個序列得到的總和已存在(被前一個所記錄)的話，就找到了

?代碼

1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 const int maxn=2e5+5; 5 map<int,pair<int,int> > mp; 6 int a[maxn]; 7 ll sum; 8 int main() 9 { 10 int k; 11 cin>>k; 12 for(int i=1;i<=k;i++) 13 { 14 int n; 15 cin>>n; 16 sum=0; 17 for(int j=1;j<=n;j++) 18 { 19 cin>>a[j]; 20 sum+=a[j]; 21 } 22 for(int j=1;j<=n;j++) 23 { 24 int x=sum-a[j]; 25 if(mp.count(x)&&mp[x].first!=i) 26 { 27 cout<<"YES"<<endl; 28 cout<<i<<' '<<j<<endl; 29 cout<<mp[x].first<<' '<<mp[x].second<<endl; 30 return 0; 31 } 32 mp[x]=make_pair(i,j); 33 } 34 } 35 cout<<"NO"<<endl; 36 } View Code

?

轉載于:https://www.cnblogs.com/MMMinoz/p/11228539.html

總結

以上是生活随笔為你收集整理的Codeforces Round #486 (Div. 3) C Equal Sums （map+pair）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。