一:
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n, sum=0, x, y;
scanf(“%d”, &n);
for (int i = 0; i < n; i++)
{
scanf(“%d %d”, &x, &y);
sum += x * y;
}
printf(“%d”, max(sum, 0));
return 0;
}
二:
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
int m = 0;
int maximum = 0;
const int M = 10010;
int main()
{
scanf(“%d”, &m);
set<int> a;
vector<pair<int, int>> q;
for (int i = 0; i < m; i++)
{
int x, y;
scanf(“%d%d”, &x, &y);
q.push_back(make_pair(x, y));
a.insert(x);
}
sort(q.begin(), q.end());
for (int i = 0; i < m; i++)
q[i].second == (q[i].first >= q[0].first ? 1 : 0) ? maximum++ : 0;
int output = q[0].first;
vector<pair<int, int>>::iterator itr = q.begin();
int sum = 0;
for (set<int>::iterator theta = a.begin(); theta != a.end(); theta++)
{
if (*theta == q[0].first)
continue;
int a = itr->first;
while (a == itr->first)
{
itr->second == 0 ? sum++ : sum–;
itr++;
}
if (sum >= 0)
{
maximum += sum;
sum = 0;
output = *theta;
}
}
printf(“%d”, output);
return 0;
}
这题也是有点意思,但不难,我认为这题的解题点在于:
1.阈值是有序的。也就是说每个阈值你不用把所有的值都从头到尾算一遍(当然前提你要先把这些阈值排序);对于每个阈值,后面的要测试的阈值都比他大,那这个阈值之前的测试结果和后面的值的测试结果是一样的,同理,每个阈值后面的测试结果,和用这个阈值之前的阈值测试的结果是一样的;那么很显然我们只需要一开始算出一个阈值结果,每次只用再拿下一个阈值来测试下一个阈值本身和前一个阈值的测试结果就行了。 其实是前缀和思想