时间限制：C/C++语言 1000MS；其他语言：3000MS
内存限制：65536KB;其他语言：589824KB
题目描述：
给定一个正整数组a,返回一个新的数组Sums,满足sums[i]的值为a重笔a[i]小的数字之和，如果不存在比a[i]小的数字，则sums[i]为0，
已知数组a中元素最大值不超过100000，数组长度不超过10000，数组元素允许重复。
输入
第一行为证书n,表示数组的长度
接下的n行数字表示数组里的元素
输出
正整数数组sums，使得sunms长度与a长度相同
样例输出
4
5
4
2
9
样例输出
6
2
0
11
非正规答案，作为参考：
#include#include#includeint main() {
std::map m;
unsigned long long n;
std::cin >> n;
if (n == 0) return 0;
std::vectorinput(n);
for (unsigned long long i = 0; i < n; i++) { std::cin >> input[i];
if (m.find(input[i]) == m.end()) {
m[input[i]] = input[i];
} else {
m[input[i]] += input[i];
}
}
unsigned long long sum = 0;
for (auto iter = m.begin(); iter != m.end(); iter++) {
unsigned long long second = iter->second;
m[iter->first] = sum;
sum += second;
}
for (unsigned long long i = 0; i < n; i++) { std::cout << m[input[i]] << std::endl; } return 0; }
时间限制：C/C++语言 1000MS；其他语言：3000MS
内存限制：131072KB;其他语言：655360KB
题目描述：
给定一个圆，圆心在原点。给定圆上一组点a[i] (i=1,2,……n),各点互相不重复，且用x轴正方向逆时针转至与该点所在半径重合时所转角度的100倍（整数）表示，取值范围是（0,36000）,
我们可以从这组点钟任选三点组成一个三角形，请问最多可以组成多少个三角形？
输入
第一行为为一个正整数，n<=1000. 接下来n行，每一行有一个整数，每个数表示在圆边上的一个点。 输出 任选三点，可以组成钝角三角形的数量
样例输入
4
0
10000
12000
18000
样例输出
2
hint
补充样例
输入样例乙
4
9
0
27000
18000
输出样例乙
0
非正规答案，作为参考：
#include#includeint main() {
int n;
std::cin >> n;
std::vectorinput(n);
std::vectorB(36000, 0);
for (int i = 0; i < n; i++) { std::cin >> input[i];
B[input[i]]++;
}
for (int i = 1; i < 36000; i++) { B[i] += B[i-1]; } unsigned long long rst = 0; int i = 0; for (; i < n; i++) { unsigned long long howmany = 0; if (input[i] < 18000) { howmany = B[input[i]+17999] - B[input[i]]; } else if (input[i] == 18000) { howmany = B[35999]-B[18000]; } else { howmany = B[35999] - B[input[i]] + B[input[i]-18001]; } rst += howmany*(howmany-1)/2; } std::cout << rst; return 0; }
QQ图片20180911190853.jpg
// 3
#include#include#include#includeint main() {
unsigned int m, n, k;
std::cin >> m >> n >> k;
std::vectorhas_rely(m+1, 0);
std::map key_release_value;
for (unsigned int i = 0; i < k; i++) { unsigned int a, b; std::cin >> a >> b;
if (key_release_value.find(b) == key_release_value.end()) {
std::vectorv;
v.push_back(a);
key_release_value[b] = v;
} else {
key_release_value[b].push_back(a);
}
has_rely[a]++;
}
std::priority_queue can_do;
for (unsigned int i = 1; i <= m; i++) { if (has_rely[i] == 0) { can_do.push(i); } } unsigned int count = 0; unsigned int days = 0; while (true) { if (can_do.size() == 0) { if (count != m) { std::cout << 'E'; } else { std::cout << days; } return 0; } std::vectorfresh_new;
unsigned int poped = 0;
while (can_do.size() != 0) {
poped++;
unsigned int job_idx = can_do.top();
can_do.pop();
fresh_new.push_back(job_idx);
if (poped == n) break;
}
count += poped;
days++;
for (auto released : fresh_new) {
for (auto can_release : key_release_value[released]) {
has_rely[can_release]--;
if (has_rely[can_release] == 0) {
can_do.push(can_release);
}
}
}
}
}
