codeforce 421D

題目連結：

http://codeforces.com/problemset/problem/421/D

D. Bug in Code

time limit per test 1 second

memory limit per test 256 megabytes

#### 問題描述

> Recently a serious bug has been found in the FOS code. The head of the F company wants to find the culprit and punish him. For that, he set up an organizational meeting, the issue is: who's bugged the code? Each of the n coders on the meeting said: 'I know for sure that either x or y did it!'

>

> The head of the company decided to choose two suspects and invite them to his office. Naturally, he should consider the coders' opinions. That's why the head wants to make such a choice that at least p of n coders agreed with it. A coder agrees with the choice of two suspects if at least one of the two people that he named at the meeting was chosen as a suspect. In how many ways can the head of F choose two suspects?

> Note that even if some coder was chosen as a suspect, he can agree with the head's choice if he named the other chosen coder at the meeting.

#### 輸入

> The first line contains integers n and p (3 ≤ n ≤ 3·105; 0 ≤ p ≤ n) — the number of coders in the F company and the minimum number of agreed people.

> Each of the next n lines contains two integers xi, yi (1 ≤ xi, yi ≤ n) — the numbers of coders named by the i-th coder. It is guaranteed that xi ≠ i,  yi ≠ i,  xi ≠ yi.

#### 輸出

> Print a single integer — the number of possible two-suspect sets. Note that the order of the suspects doesn't matter, that is, sets (1, 2) and (2, 1) are considered identical.

#### 樣例

> **sample input**

> 4 2

> 2 3

> 1 4

> 2 1

> **sample output**

> 6

題意

對于特定的兩個人(u,v)如果有至少p個人認為其中的一個是buger，那麼這兩個人就有可能被叫到辦公室。現在叫你求所有滿足條件的(u,v)。

我們用agr[i]表示質疑i的人數，mp[u,v]記錄同時質疑u、v的人數。那麼對于(u,v)隻要滿足agr[u]+agr[v]-mp[u,v]>=p，就有可能被叫到辦公室。

為了快速計算結果，這裡我們做個轉換、ans=sigma(agr[u]+agr[v]>=k)-sigma(agr[u]+agr[v]-mp[u,v]<k)對于agr數組，我們排個序，就能O(n)時間統計出sigma(agr[u]+agr[v]>=k)。而sigma(agr[u]+agr[v]-mp[u,v]<k)隻要掃一遍mp裡面的元素就可以了。

代碼

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
#define X first
#define Y second
#define mkp make_pair
using namespace std;

const int maxn = 3e5 + 10;
typedef __int64 LL;
int n, m;

int agr[maxn];
map<pair<int, int>, int> mp;
map<pair<int, int>, int>::iterator iter;

int main() {
	memset(agr, 0, sizeof(agr));
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		if (u > v) swap(u, v);
		agr[u]++; agr[v]++;
		mp[mkp(u, v)]++;
	}
	LL ans = 0;
	for (iter = mp.begin(); iter != mp.end(); iter++) {
		int u = (iter->X).X, v = (iter->X).Y, cnt = iter->Y;
		if (agr[u] + agr[v] >= m&&agr[u] + agr[v] - cnt < m) ans--;
	}
	sort(agr + 1, agr + n + 1);
	//for (int i = 1; i <= n; i++) printf("%d ", agr[i]);
	//printf("\n");
	int st = 1, ed = n;
	for (; st < n; st++) {
		while (ed > st&&agr[st] + agr[ed] >= m) ed--;
		ans += min(n - ed,n-st);
	}
	printf("%I64d\n", ans);
	return 0;
}
           

雜七雜八

這一題最關鍵的地方就是模組化吧！把問題轉換成求agr[u]+agr[v]-mp[u,v]。進而利用一些算法和套路來解決實際問題。