【CSU-1315】解题报告（排序，前缀和）

原始题目

1315: 全场最水题之陈兴老师与比赛

  • Time Limit: 1 Sec
  • Memory Limit: 128 Mb
  • Submitted: 841
  • Solved: 280

Description

大家都知道ACM比赛罚时很重要。比如说你做A题要10分钟，B题要15分钟，如果先做A题再做B题，那么在ranking上的时间就是10 + （10）+ 15 = 35。如果先做B题再做A题总罚时就是15+(15)+ 10=40.现在陈兴老师要做一场比赛，比赛有\(n\)道题， 总时间是\(300\)分钟。 我们的陈兴老师仅仅看题目就可以知道他做每道题需要的时间，所以他想在比赛刚开始时就计算出自己的最大总做题数，以及对应的总罚时和做题顺序（当然，做题数相等时当然希望总罚时最少咯）。 比如一般的比赛，陈兴老师做第一题需要1分钟，第二题2分钟，依此类推，陈兴老师只需要66分钟就可以AK一场11道题的比赛。PS: 陈兴老师做题都是1Y，膜拜陈兴老师Orz！

Input

第一行是一个数字 \(n (0<n ≤25)\) 。

第二行是\(n\)个数字，第\(i\)个数字代表陈兴老师出编号为\(i\)的题所需要的时间 \(t_i( 0 < t_i ≤ 80)\)。

Output

第一行输出陈兴老师的出题数和Penalty（总时间）

以下按照顺序输出陈兴老师出题的顺序,每行一个编号。（详见输出样例）PS：时间一样的按编号升序输出。

Sample Input

3
1 2 3
4
1 2 3 4
6
60 60 60 60 60 60

Sample Output

3 10
1
2
3
4 20
1
2
3
4
5 900
1
2
3
4
5

Hint

Source

题目大意

原题说的不大清楚，实际上对于每到AC题目罚时累加上从开始到完成该题目的时间，比赛一共300分钟， 求解题数，罚时，并输出接替顺序。（感觉整理CSU题面的时候应该再完善一下题目意思）

解题思路

排序以后求前缀和，当前缀和超过300时输出

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <set>
#include <queue>
#include <map>
#include <sstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <cmath>
#define rep(i,a,n) for(int i=a;i<n;++i)
#define per(i,a,n) for(int i=n-1;i>=a;--i)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define np next_permutation
#define all(x) x.begin(),x.end()
#define insert(x) x,x.begin()
#define cl(x,a) memset(x,a,sizeof(x))
using namespace std;
const int maxn=1e5+5;
const int maxm=1e5+5;
const int maxl=26;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<string,string> pss;

bool cmp(pii a,pii b){
	if(a.second!=b.second) return a.second<b.second;
	else return a.first<b.first;
}

int n,t,a[maxn];
int main(){
//	ios::sync_with_stdio(false);
	while(~scanf("%d",&n)){
		vector<pii> v;
		rep(i,1,n+1){
			int temp;
			scanf("%d",&temp);
			
			v.pb(mp(i,temp));
		}
		sort(all(v),cmp);
		a[0]=v[0].second;
		rep(i,1,n) {
			a[i]=a[i-1]+v[i].second;
//			cout<<"a["<<i<<"] = "<<a[i]<<endl;
		}
		int panality=0,i=0,caltime=0;
		for(;i<n&&caltime<=300;i++){
			panality+=a[i];
			caltime+=v[i].second;
		}
		if(caltime<=300) {
//			cout<<n<<" "<<panality<<endl;
			printf("%d %d\n",n,panality);
//			rep(i,0,n) cout<<v[i].fi<<endl;
			rep(i,0,n) printf("%d\n",v[i].fi);
		}
		else {
			panality-=a[--i];
//			cout<<i<<" "<<panality<<endl;
			printf("%d %d\n",i,panality);
//			rep(i,0,n) cout<<v[i].fi<<endl;
			rep(j,0,i) printf("%d\n",v[j].fi);
		}
		
		
	}
}

收获与反思

排序一下